RE: Re: Re: Re: An interesting math problem
- To: mathgroup at smc.vnet.net
- Subject: [mg36385] RE: [mg36349] Re: [mg36185] Re: [mg36125] Re: An interesting math problem
- From: "DrBob" <drbob at bigfoot.com>
- Date: Wed, 4 Sep 2002 02:56:42 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
By taking sums and differences of the counterweights 1, 3, ... 3^(k-1) you can precisely express all integers up to the integer whose base 3 notation is composed of k ones. By doubling those counterweights, you can precisely express all the EVEN integers up to TWICE that limit, or -1 + 3^k. If you know that unknowns are limited to the integers from 1 to 3^k, this allows you to precisely weight the even numbers and bracket the odd numbers. Hence counterweights 2, 6, ... 2*3^(k-1) are sufficient for unknowns up to 3^k. Notice that this is an efficient coding scheme: Each counterweight is multiplied by -1, 0, or 1, so there can be at most 3^k distinct counterweight sums. More than half are negative or zero, however; the positive sums and differences number at most (3^k - 1)/2. Since we need to enumerate (and CAN enumerate with even weights) only the even numbers and because we get the maximum unknown 3^k by elimination, we "cover" up to twice as many as we can enumerate, plus one. Twice (3^k - 1)/2 plus one is 3^k, so we're getting the maximum coverage possible for a given number of counterweights. Bobby Treat -----Original Message----- From: Julio Vera [mailto:jvera at adinet.com.uy] To: mathgroup at smc.vnet.net Subject: [mg36385] [mg36349] Re: [mg36185] Re: [mg36125] Re: An interesting math problem I liked this very much. For n=4 there are 3^n=81 possible combinations, but only 40 positive ones - the rest would be 0 and each of the positive ones multiplied by -1. As Bob stated, this is obtained by: (3^n-1)/2=40 For these 40 positive integers to match 1 to 40 correspondingly, the biggest should be 40 (also, the smallest should be 1). So we have: a+b+c+d=40 or 1+b+c+d=40 (we state that a<b<c<d) This could be a particular case (for a=3 and n=4) of: In[1]:= Sum[a^i , {i, 0, n - 1}] == (a^n-1)/(a-1) Out[1]= True With 5 counterweights, we would be able to determine the weight of 121 elements In[]:= n = 5; a = 3; (a^n - 1)/(a - 1) Out[]= 121 And the 5 counterweights would be the 5 elements of the corresponding sum. In[]:= Table[a^h, {h, 0, n - 1}] Out[]= {1, 3, 9, 27, 81} I did not understand what Bryan said about 2,4,10,28 being a solution. At first, I thought b could be either 2 or 3. b, the second of the 40 positive combinations, could be b=2 or b-a=2, meaining b=3 But, if b=2, we would have 2 of the 40 positive combinations that would equal 1: a=1 and b-a=1 This means we would not be able to get all 40 values with the 40 positive combinations. so b must be 3. Maybe the same reasoning would lead to 9 and 27 being also unique. {1,3,9,27} could be the most "efficient" solution (of a+b+c+d=40), in the sense that it would not generate any repetition. And the most efficient solution would be the only solution, since the repetitions are not acceptable. I did not understand, either, what Bob said about 34 being the largest possible weight. I am very curious about these two issues (a second solution, and 34), so I would very much appreciate if you could elaborate on them. Thanks very much, Julio ----- Original Message ----- From: <BobHanlon at aol.com> To: mathgroup at smc.vnet.net Subject: [mg36385] [mg36349] [mg36185] Re: [mg36125] Re: An interesting math problem > > In a message dated 8/22/02 6:23:12 AM, timreh719 at yahoo.com.tw writes: > > >I'm sorry for that my question is not clear,I have correct below. > > > >timreh719 at yahoo.com.tw (bryan) wrote in message > news:<ajvp7h$ibk$1 at smc.vnet.net>... > >> Hi All: > >> I have a very interesting math problem:If I have a scales,and I > >> have 40 things that their mass range from 1~40 which each is a nature > >> number,and now I can only make 4 counterweights to measure out each > >> mass of those things.Question:What mass should the counterweights > >> be??? > >> The answer is that 1,3,9,27 and I wnat to use mathematica to solve > >> this problem. > >> In fact,I think that this physical problem has various > >> answer,ex.2,4,10,28 > >> this way also work,because if I have a thing which weight 3 , and I > >> can measure out by comparing 2<3<4 . But,If I want to solve this math > >> problem: > >> {x|x=k1*a+k2*b+k3*c+k4*d}={1,2,3,4,,,,,,40} where a,b,c,d is nature > numbers. > >> and {k1,k2,k3,k4}={1,0,-1} > >> How to solve it ?? > >> Thank you very much in advance and hope mail to me your method and > >> mathematica solving method. appreciate any idea sharing > >> sincerely > >> bryan > > > > Just use brute force. > > Needs["DiscreteMath`Combinatorica`"]; > > var = {a, b, c, d}; n = Length[var]; > > s = Outer[Times, var, {-1, 0, 1} ]; > > f = Flatten[Outer[Plus, Sequence@@s]]; > > Since the length of f is just 3^n then the range of numbers > to be covered should be {-(3^n-1)/2, (3^n-1)/2}. > Consequently, the largest of the weights can not exceed > (3^n-1)/2 - (1+2+...+(n-1)) or > > ((3^n-1) - n(n-1))/2 > > 34 > > Thread[var->#]& /@ > > (First /@ Select[{var,f} /. Thread[var->#]& /@ > > KSubsets[Range[((3^n-1) - n(n-1))/2], n], > > Sort[#[[2]]] == Range[-(3^n-1)/2,(3^n-1)/2]&]) > > {{a -> 1, b -> 3, c -> 9, d -> 27}} > > > Bob Hanlon > Chantilly, VA USA >