Re: Re: An interesting math problem
- To: mathgroup at smc.vnet.net
- Subject: [mg36191] Re: [mg36125] Re: An interesting math problem
- From: BobHanlon at aol.com
- Date: Mon, 26 Aug 2002 04:16:13 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
In a message dated 8/24/02 2:49:38 PM, writes:
>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}}
>
A modification to my earlier response. Since you are try to cover all of
the values up to (3^n-1)/2 then you can speed up the brute force method by
requiring that a+b+c+d == (3^n-1)/2
Needs["DiscreteMath`Combinatorica`"];
var = {a,b,c,d}; n = Length[var]; m = (3^n-1)/2;
s = Outer[Times, var, {-1,0,1} ];
f = Flatten[Outer[Plus, Sequence@@s]];
k= Select[KSubsets[Range[m - n(n-1)/2], n],
(Plus @@ #) == m&];
Thread[var->#]& /@
(First /@ Select[{var,f} /. Thread[var->#]& /@ k,
Sort[#[[2]]] == Range[-m,m]&])
{{a -> 1, b -> 3, c -> 9, d -> 27}}
Bob Hanlon
Chantilly, VA USA