Weighing in 89 different ways

Question

On the table, there is a balance with two pans together with ten weights ofrespectively 1, 2, 4, 8, 16, 32, 64, 128, 256 and 512 grams. Cosmo takes a coin out of his pocket, shows it to Fredo and says: "There are exactly 89 different ways of placing the coin together with some (perhaps zero) of the weights into the left pan and placing some of the other weights into the right pan, so that the balance is in equilibrium."

Question: What is the weight of Cosmo's coin?

Answer 1

The weight of Cosmo's coin is

$341$, or represented as a binary number $101010101$.

Carl Löndahl found the second solution $171$.

Step 1

This image represents both sides of the scale, the colored part being the coin splitted in the corresponding weights. The part below demonstrates distribution of the weights for some possible weighings. In this case we only change the weights 256 and 512 ("bits" 8 and 9), and ignore changes in the rest of the bits. There are 2 possible cases. Let's call this number: $$S_1=2$$

Step 2

This time we look at the weights 128 and 64 ("bits" 6 and 7). We have again 2 possible cases. For each of the 2 cases we can choose 1 possible case from step 1 above which gives us together $2 * S_1$ cases.



But we have 1 additional case if we use all four "bits" 6 to 9. This gives us a new number: $$S_2=2*S_1+1=5$$

Step 3

Again 2 cases, this time using bits 4 and 5. Both can be combined with all cases from step 2.



One additional case using bits 4 to 7 which can be combined with all cases from step 1.



And one more case using bits 4 to 9. This gives us a total of: $$S_3=2*S_2+S_1+1=13$$

Step 4

Similar to previous chapters we can define: $$S_4=2*S_3+S_2+S_1+1=34$$

Step 5

I omitted the picture here as the pattern should be obvious now: $$S_5=2*S_4+S_3+S_2+S_1+1=89$$

Second solution (found by Carl Löndahl)

The nubmer of weighings can be calculated similarly for this number.


$$S_1=3$$


Here we see a difference, there are 2 cases without using bits 5 and 6, and this is also true for the following steps.$$S_2=2*S1+2=8$$ $$S_3=2*S_2+S_1+2=21$$ $$S_4=2*S_3+S_2+S_1+2=55$$ There is also a difference in the 5th step. Because bit 1 is already used we multiply with 1 instead of 2 here. $$S_5=1*S_4+S_3+S_2+S_1+2=89$$

General solution

Based on the thoughts above we can define a general way to calculate the number of weighings. First write the number in binary form. Then define a variable for each bit equal 1 from left to right as follows:

$x_1$ -> number of weights bigger or equal the value of the first set bit
$x_2$ -> number of remaining weights bigger or equal the value of the second set bit
$x_3$ -> number of remaining weights bigger or equal the value of the third set bit
...

The number can be then calculated as follows:
$$S_1 = x_1$$ $$S_2 = x_2*S_1+(x_1-1)$$ $$S_3 = x_3*S_2+(x_2-1)*S_1+(x_1-1)$$ $$S_4 = x_4*S_3+(x_3-1)*S_2+(x_2-1)*S_1+(x_1-1)$$ $$S_5 = x_5*S_4+(x_4-1)*S_3+(x_3-1)*S_2+(x_2-1)*S_1+(x_1-1)$$

Answer 2

Turns out there are two solutions: $171$ and $341$ (unless I made a terrible mistake; I have checked this using some Python code).

L = [1,2,4,8,16,32,64,128,256,512]
Q = [0]*(sum(L)+1)
def rec(Q, L, i, s, f):
    if i == len(L):
        if s > 0:
            Q[s] += 1
        if s == 171: # change to see sets for 341
            print f, sum(f)
        return
    f.append(L[i])
    rec(Q, L, i+1, s + L[i], f)
    f.pop()
    f.append(-L[i])
    rec(Q, L, i+1, s - L[i], f)
    f.pop()
    rec(Q, L, i+1, s, f)
rec(Q,L,0,0,[])
print "Possible solutions:"
for i in range(0,len(Q)): 
    if Q[i] == 89: print i