Weight Problem

[Gabriel Genellina]

En Sat, 15 Mar 2008 18:57:36 -0200, Ravi Kumar <ra21vi at gmail.com> escribi�:

> An Interesting problem,
> """
> A man has only 4 bricks of different weights, lies between 1-40KG,
> Also, the total weights of Brick A, B, C, D (ie A+B+C+D) is 40KG.
> The man uses that brick to calculate every possible weight
> from 1 KG to 40 KG in  his shop. (only whole numbers 1KG, 2KG etc, not  
> like
> 2.3KG)
> """
>
> I thought it would really be good to solve it by python, and right now on
> the mid-way solving using very dirty approach.
> But I feel, using SETs with python in such would solve it better.
> Can anyone come with good solution, and maybe solution showing usage of
> Sets.

This isn't specifically Python problem; some hints anyway:

a) Any integer can be written as a base-3 number (anyone knows base-10  
numbers, and you know base-2/binary numbers, I presume).

x = a[n]*3**n + a[n-1]*3**(n-1) + ... + a[1]*3 + a[0]

where all a[i] are either 0, 1 or 2

b) 2*3**n = (3-1)*3**n = 3**(n+1) - 3**n

So you can replace every a[i]==2 in the a) expression with (-1), adding +1  
to the coefficient to the left (why?). You end up with an expression  
involving only +1 and -1 coefficients (why?)

c) You can compare, add and substract weights using an old two-plate  
balance.

-- 
Gabriel Genellina