MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: RE: RE: How do I create a such List?
  • Next by Date: RE: CirclePlus precedence and bigoplus
  • Previous by thread: Re: Re: An interesting math problem
  • Next by thread: function mySet[]