7
$\begingroup$

Cosmo puts a golden weight of 11111 gram into the right pan of a balance. Then Fredo starts adding his bronze weights to the balance:

  • first Fredo adds a bronze weight of 1 gram to one of the pans;
  • then he adds a bronze weight of 2 gram to one of the pans;
  • then he adds a bronze weight of 4 gram to one of the pans;
  • then he adds a bronze weight of 8 gram to one of the pans;
  • and so on.

Every bronze weight weighs twice as much as the preceding one. After Fredo has been doing this for some time, the two pans are in equilibrium.

(a) Is it possible that Fredo has put the 16 gram bronze weight into the left pan?
(b) Is it possible that Fredo has put the 16 gram bronze weight into the right pan?

$\endgroup$
5
$\begingroup$

Adding a weight to the left pan is the same as adding that weight to the right pan and twice that weight to the left pan. So we can treat adding the first $n$ powers of two to the pans the same as if we added all of them to the right pan, and double some of them to the left pan.

So we have added $2^n - 1$ to the right pan, and some even but otherwise arbitrary binary number of up to $n+1$ digits to the left pan. Calling the starting weight $x$, to balance the scales we need $2(2^n - 1) \ge x + 2^n - 1$, which means $2^n - 1 \ge x$. So we must add a number with at least as many binary digits as the starting number. The desired number on the left will be $ x + 2^n - 1$, and we interpret it as follows: divide by 2; each bit in the result represents a weight on the left, each 0 represents a weight on the right. (Incidentally, this shows that you can't do this trick with an even starting weight).

11111 decimal expands to 10101101100111 binary. So we must add 11111111111111 to it, getting 110101101100110.

Divide by 2 to get 11010110110011, and we see that the bit representing 16 is set, so 16 is on the left.

Now, if we use a larger value of $n$, it will still work; but it won't change any of the original $n$ digits in our generated number (since adding powers of two does not change the lower bits in a binary number).

Therefore, 16 cannot be anywhere but on the left.

Answers:

a) Yes
b) No.

Edit: there is no limit to the number of weights that can be added. Once we have an equilibrium, consider the largest weight ($2^n$ for some $n$), which is on side A (whatever side that happens to be). The next weight to be added is $2^{n+1}$. We simply shift the $n$th weight to side B; this reduces side A by $2^n$ and increases side B by $2^n$, a net difference of $2^{n+1}$. Now we put the new weight on side A, increasing it again by $2^{n+1}$, and restoring the balance. However, this only moves the heaviest weight; all the others stay where they are. So once a weight is no longer the heaviest, it never moves again. (Cosmo doesn't move weights, but the logic still applies).

$\endgroup$
  • $\begingroup$ I think your answer would be best summarized by just focusing on the fact that you have to add 11111111111111 (binary) to the original amount then divide by 2. $\endgroup$ – JonTheMon Feb 10 '15 at 17:56
  • $\begingroup$ The idea was to also explain where that amount came from, and to show that none of the other solutions would change the result for the weight of 16. $\endgroup$ – Callidus Feb 11 '15 at 7:09
6
$\begingroup$

The binary of 11111 is 010 1011 0110 0111 and the other pan is effectively 000 0000 0000 0000. Adding the weights is the same as adding 1 to each spot, and we want the two numbers to end up the same.

The scenario that we must avoid is having 0 0 and needing to add a weight to one side or the other. So, if the next digit on the right pan is 0, add your current weight to the right pan. Otherwise, add it to your left pan.
So you'd end up with (orig, left, right):
010 1011 0110 0111
011 0101 1011 0011
011 0101 1011 0011
= 13747

Now where the 16 weight can go, let's look at that part of the sequence: 10 0111 where 16 = 01 0000. The only way we can add the 16 to the right pan is if there is a 1 there already (e.g. 11 0011). But, if we add it to the right, that violates our "look ahead and see 0" rule. So:
a) yes
b) no

Process:

010 1011 0110 0111
000 0000 0000 0000
                 - See 1 (left)
010 1011 0110 0111
000 0000 0000 0001
                -  See 1 (left)
010 1011 0110 0111
000 0000 0000 0011
               -   See 0 (right)
010 1011 0110 1011
000 0000 0000 0011
              -    See 0 (right)
010 1011 0111 0011
000 0000 0000 0011
            -      See 1 (left)
010 1011 0111 0011
000 0000 0001 0011
           -       See 1 (left)
010 1011 0111 0011
000 0000 0011 0011
          -        See 0 (right)
010 1011 1011 0011
000 0000 0011 0011
         -         See 1 (left)
010 1011 1011 0011
000 0000 1011 0011
       -           See 1 (left)
010 1011 1011 0011
000 0001 1011 0011
      -            See 0 (right)
010 1101 1011 0011
000 0001 1011 0011
     -             See 1 (left)
010 1101 1011 0011
000 0101 1011 0011
    -              See 0 (right)
011 0101 1011 0011
000 0101 1011 0011
  -                See 1 (left)
011 0101 1011 0011
001 0101 1011 0011
 -                 Just 1 remaining (left)
011 0101 1011 0011
$\endgroup$
6
$\begingroup$

Fredo's weights are $1_2, 10_2, 100_2, ...$, so writing the sum of a subset of the weights written in base 2 gives an easy way to identify the individual weights visually. For example, if he placed the 8g, (not 4g), 2g and 1g weights into the left pan, the sum of the weights is $1011_2$ or $11_{10}$. The right pan would then get the complement, namely $0100_2$, which we can get by subtracting from $1111_2$.

Let $n$ be the sum of the weights Fredo puts in the left pan.

Given a $k$-digit base-2 number $n$, let us call its complement $C(n,k)$. Then $C(n,k) = (2^k - 1) - n$.

How many weights did Fredo use (i.e. what is $k$)? Since $11111$ has 14 digits in base 2, the weights in the left pan must also have at least 14 base-2 digits to balance. If Fredo used 16 weights, the largest would tip the scale whichever side it was placed, so $k$ is either $14$ or $15$.

The 16g weight is in the right pan if and only if $n$ has a $0$ in position 5 since $16_{10} = 10000_2$.

Now, suppose Fredo used $k$ weights and puts a subset weighing $n$ grams into the left pan. Then the right pan would receive the remaining weights, $C(n,k)$ grams. For the pans to balance, we require (writing now in base-10 for simplicity):

$n = 11111 + C(n,k) = 11111 + 2^k - 1 - n$, which gives $n = (11110 + 2^k)/2$.

When $k=14$ we have $n=13747$, and when $k=15$ we have $n=21939$. In both cases, writing $n$ in base 2 shows a '1' in position 5, so the 16g weight is always in the left pan.

So the answer is (a) yes and (b) no.

$\endgroup$
  • 1
    $\begingroup$ What happens if the right pan starts with a 1 in the 5th position, say 11127? With k=14 or 15 both of the n have a 1 in the 5th position. Does this mean that only the iff condition changes? If this is the case you should mention that that condition depends from the initial state of the plates, no? $\endgroup$ – Narmer Feb 10 '15 at 13:43
  • $\begingroup$ @Namer Sorry for the delay - I'm new here and didn't have enough rep points previously to reply. I have edited my answer to clarify. By defining $n$ on the left pan, the answer is independent of the initial state of the right pan. $\endgroup$ – Lawrence Feb 14 '15 at 13:17
5
$\begingroup$

The possible answer is:

1______11111
2__________4
16_________8
32________64
128______512
256_____2048
1024
4096
8192

This will balance the scales at

13747g

So to answer your questions:

(a) Yes, it is possible
(b) No, it's impossible. Proof:

11111 can be made from those bronze weights by adding the following ones: 8192, 2048, 512, 256, 64, 32, 4, 2, 1. From there we can find out that we still need 4096, 1024, 128, 16 and 8.
If Cosmo would add 16 on the right scale, we would get 11127 on the right scale. To get that we would need 8192, 2048, 512, 256, 64, 32, 16, 4, 2 and 1 weights. But 16 is already on the right pan, so we can't use it on the left.

$\endgroup$
  • 1
    $\begingroup$ Your answer is correct for a. But I think the proof you gave for b is incorrect. You don't need to reach 11127, since you will put some more weights on this side. $\endgroup$ – Kalissar Feb 10 '15 at 11:10
  • $\begingroup$ @Kalissar I thought that my proof wasn't fully correct, but I couldn't come up with a better one(yet) $\endgroup$ – Novarg Feb 10 '15 at 11:11
4
$\begingroup$

11111 in binary is 0010 1011 0110 0111. Instead 16 is 0001 0000. In order to have the same amount in both plates, the binary rapresentation of the weight must be the same:

R: 0010 1011 0110 0111 //We need a 1 in 5th position.
L: 0000 0000 0001 0000 

If we add 1 in the R plate we get 0010 1011 0110 1000, we then add 8 to get the 1 in 5th position. But then we have to add 2 and 4 in the plates and since the weights are increasing we would degenerate in an incompatible configuration:

Last 4 digits
R: 0000 add 4 or 2 -> 0100 or 0010
L: 0000 will never be possible to reach the 0100 or 0010 configuration (I only have 2 or 4 respectively)

This leads to the only configuration possible:

R: 0010 1011 0111 0011 added 4, 8
L: 0000 0000 0001 0011 added 1, 2, 16

We cleared powers from 0 to 4. The same reasoning applies to the rest of the binary number:

R: 0010 1011 1011 0011 added 64
L: 0000 0000 1011 0011 added 32, 128

R: 0010 1101 1011 0011 added 512
L: 0000 0101 1011 0011 added 256, 1024

R: 0011 0101 1011 0011 added 2048
L: 0011 0101 1011 0011 added 4096, 8192

And we're done. The plates are now in equilibrium and weight:

R = 11111 + 4 + 8 + 64 + 512 + 2048 = 13747
L = 1 + 2 + 16 + 32 + 128 + 256 + 1024 + 4096 + 8192 = 13747

So the first answer is yes.

In case we put the 16 in the right plate, using the same approach:

R: 0010 1011 0111 0111
L: 0000 0000 0000 0000 

Now we need to get a 1 in the 5th place in the left plate, but we can't since the only way is via remainder and we don't have a "one" in the left plate. We are in a incompatbile configuration:

R: 0010 1011 0111 0111
L: 0000 0000 0000 1111 we don't have any way to put a 1 in the 5th position 

So the answer for the second question is no.

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