10
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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

enter image description here

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

enter image description here

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.

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

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.

enter image description here
$$S_1=3$$
enter image description here

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)$$

$\endgroup$
  • $\begingroup$ Is this really unique? Isn't $512-341=171$ a solution as well? $\endgroup$ – Carl Löndahl Nov 14 '15 at 22:37
  • 1
    $\begingroup$ @CarlLöndahl You are of course correct, I expected a unique solution. Added a calculation for 171 and also a general solution. $\endgroup$ – Sleafar Nov 15 '15 at 12:46
8
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.