Puzzle : Balls and Binary

Well,

I know that the name does not give any clue what the puzzle is about, but I could not think of any better name than this. Anyways, without any beating around the bush, let me directly come to the point.

Oh, for the record, this nice puzzle was given to me by manoj.

Problem : There are boxes, numbered from 0 to $\infty$ . There is a ball placed in box 0. In addition to this, you are given k-balls. You can add or remove a ball from box numbered j only if there is a ball in the box numbered j-1. Now, using only given k-balls and the valid moves ( add/remove ), how would you place a ball in the box numbered $2^k - 1$ ?

Solution : I have to get back to a very powerful mathematical tool called principle of mathematical induction for this problem. Of course, the trick lies in coming up with correct induction hypothesis.

Claim : Using k-balls I can reach a configuration where balls are placed in box numbered

$2^{k-1},2^{k-1} + 2^{k-2}, 2^{k-1}+2^{k-2} + 2^{k-3}, \dots ,2^k - 2, 2^k - 1$ . Note that, according to this claim, i-th ball will be $2^{k-i}$ distance away from (i-1)-th ball.

Base case : k = 1, I have only one ball and I will place it in box numbered 1. Configuration will look like following : ( a box containing a ball will be written as nB)

0B 1B

So, the claim is trivially true here. Note, that 0 contains a ball by default.

Induction Hypothesis : Assume that with k = p-1 balls, balls will be positioned in box numbered :

$2^{p-2}, 2^{p-2}+2^{p-3}, \dots , 2^{p-1} - 2 , 2^{p-1} - 1$

Induction Step : We have k-balls. Using k-1 balls we can reach a configuration ( due to induction hypothesis ) where these k-1 balls are placed in boxes numbered :

$2^{k-2}, 2^{k-2}+2^{k-3}, \dots , 2^{k-1} - 1$ .

But, I still have one additional ball, I can put it in box $2^{k-1}$ as there is a ball in box $2^{k-1}-1$ . Now, I can remove a ball from $2^{k-1}-1$ because there is a ball in $2^{k-1}-2$ .

So now, I have one ball remaining, also there is a ball in $2^{k-1}-4$ . I can place a ball at $2^{k-1}-3$ and now remove a ball from $2^{k-1}-2$ and then from $2^{k-1}-3$ .

I have two balls now. There is a ball in box numbered $2^{k-1}-8$ . Using two balls, I can reach upto 3 from number 0. So, I can reach upto $2^{k-1}-5$ . Now I can recover $2^{k-1}-4$ . and so on. It is easy to see that in similar fashion I can recover k-1 balls keeping one ball in $2^{k-1}$ .

From 0 with k-1 balls in hand, I can reach upto $2^{k-1}-1$ . So from $2^{k-1}$ with k-1 balls in hand we can reach upto $2^k - 1$ . Also, it is easy to see that now balls will be place in boxes :

$2^{k-1}, 2^{k-1} + 2^{k-2}, \dots, 2^k - 2, 2^k - 1$ . If you don’t understand why this will happen, just subtract $2^{k-1}$ from above terms and you will reach configuration mentioned in induction hypothesis.

Those who are a bit confused due to bad writing as well as mathematical notation here is an example.

Example : 4 balls.

0B -> 0B 1B -> 0B 1B 2B -> 0B 2B -> 0B 2B 3B -> 0B 2B 3B 4B -> 0B 2B 4B -> 0B 1B 2B 4B -> 0B 1B 4B -> 0B 4B — using the steps show above, just asume that 4B acts like a 0B –> 0B 4B 6B 7B -> 0B 4B 6B 7B 8B -> 0B 4B 5B 6B 8B -> 0B 4B 5B 8B -> 0B 4B 8B -> 0B 1B 4B 8B -> 0B 1B 2B 4B 8B -> 0B 2B 3B 4B 8B -> 0B 1B 2B 3B 8B -> 0B 1B 2B 8B -> 0B 1B 8B -> 0B 8B ( Now you have 3 balls in your hand , assume 8B is 0B and you can reach upto 15B ).

Very nice puzzle indeed I must say 🙂 One can see its connection with binary representation of a number.

–Saurabh Joshi

3 Responses to “Puzzle : Balls and Binary”

Ramesh Says:
November 17, 2008 at 11:36 pm | Reply
Very nice, indeed.
Ramesh Says:
November 24, 2008 at 3:58 am | Reply
Can this problem be reformulated as a string rewriting system like Conway’s checker jumping?
Saurabh Joshi Says:
November 25, 2008 at 7:15 am | Reply
Well, I don’t see much connection between Conway checker and this problem. The reason is that number of checkers decrease at each move in conway checker which is not the case over here.

But yeah, thanks for bringing it up. I got a nice read at

http://www.math.uwaterloo.ca/~dgwagner/MATH249/conway.pdf

Me, Myself and Mathematics