# Puzzle: Dropping balls along the way

A man has some balls in his pocket. Let the number of balls in his pocket be $n$.(Consider $n$ as an integer. If any decimal value occurs, consider its floor value. For example, if $n$ = 2.6 then take it as 2). For every mile that he runs, he is left with half the number of balls.

For instance, if initially he has 10 balls.

After running the first mile he'll have 5 balls.
After running the second mile, he'll have 2 balls.
After running the third mile, he'll have 1 ball.
After running the fourth mile, he'll have 0 balls.

So, it takes 4 miles to lose all the balls.

So how many miles does he have to run, in order to lose $n$ balls.

-
Try it first for 16 and 32 balls. What happens with a number of balls between 16 and 32? – Phira Nov 27 '12 at 13:04
For 16 balls, 8->4->2->1->0 So he has to travel 5 miles. For 8 32 balls, 16->8->4->2->1->0 So he has to travel 6 miles. – The Programmer Nov 27 '12 at 13:09
Phira gives good advice. However, just a technicality: following your definition, he may never lose all balls. If he is left with 1 ball, half of it will be 0.5, which according to the definition will be wound down to 0. So, he will lose 0 balls (half the number he has). I believe just changing the wording to "..he is left with half the balls..." instead of "... he loses half the balls ..." will suffice. – Paresh Nov 27 '12 at 13:11
@Paresh That would also match the example, where 3 of 5 balls are lost. – Hagen von Eitzen Nov 27 '12 at 13:13
@Paresh Thank you for the suggestion Paresh – The Programmer Nov 27 '12 at 13:24
show 1 more comment

Find a pattern

I start with a chart to get an idea of a pattern:

Balls        Miles
0            0
1            1
2            2
3            2
4            3
5            3
6            3
7            3
8            4
9            4
10           4
11           4


Guess and check on a formula

You might notice a pattern already. Whenever we hit a number of balls thats a power of 2, the number of miles increases by one. Let's do another chart, with my guess of a formula:

Balls        Miles     log2(n)              Floor
1            1         log2(1)+1  = 1       1
2            2         log2(2)+1  = 2       2
3            2         log2(3)+1  = 2.58    2
4            3         log2(4)+1  = 3       3
5            3         log2(5)+1  = 3.32    3
6            3         log2(6)+1  = 3.58    3
7            3         log2(7)+1  = 3.81    3
8            4         log2(8)+1  = 4       4
9            4         log2(9)+1  = 4.17    4
10           4         log2(10)+1 = 4.32    4
11           4         log2(11)+1 = 4.46    4
12           4         log2(12)+1 = 4.58    4
13           4         log2(13)+1 = 4.70    4
14           4         log2(14)+1 = 4.81    4
15           4         log2(15)+1 = 4.91    4
16           5         log2(16)+1 = 5       5
17           5         log2(17)+1 = 5.09    5


So the formula ⌊log2(n)+1⌋ looks like a good fit. I came up with log2(n) since that undoes 2^n, which is the pattern I noticed in the first chart.

I started by trying ⌊log2(n)⌋ and ⌈log2(n)⌉, but I noticed they were a little off, so I made some changes until I finally arrived at ⌊log2(n)+1⌋.

Try it out

Try it with decimals. Try it with larger numbers. I did in my head, just to make sure this is really the correct answer.

-

Assume $n$ is written in base $2$,

$$n = \sum_{k = 0}^s a_k 2^k = \overline{a_s \ldots a_1 a_0}^2$$

If $u_t$ is the number of balls after $t$ miles, then $u_0 = n$, and $u_{t+1} = \left\lfloor\frac{u_t}{2}\right\rfloor$. You can easily check that

$$\begin{eqnarray*} u_0 &=& \overline{a_s \ldots a_2 a_1 a_0}^2 \\ u_1 &=& \overline{a_s \ldots a_2 a_1}^2 \\ u_2 &=& \overline{a_s \ldots a_2}^2 \\ \vdots & & \vdots \\ u_s &=& \overline{a_s}^2 \end{eqnarray*}$$

So he has to run $s+1$ miles to lose all the balls (which is the number of digits of $n$ in base $2$). Now the inequality $2^s \le n < 2^{s+1}$ yields the formula $s = \lfloor \log_2(n) \rfloor$. So finally the answers is $\lfloor \log_2(n) \rfloor + 1$.

-

Let $a_k$ be the number of balls in the man's pocket after $k$ miles. Thus, for the example: $$a_0 = 10$$ $$a_1 = 5$$ $$a_2 = 2$$ $$a_3 = 1$$ $$a_4 = 0$$

The general form for $a_k$ is: $$a_k = \left \lfloor \frac{a_{k-1}}{2} \right \rfloor$$

Thus, the puzzle can easily be solved in O(n) time (for programming)...

To prove it in constant time, you need to find the number of times you can perform integer division by 2 before reaching 0. This makes me think it could be something similar to $log_2(n)$.

A quick check with a program shows that computing $$\lceil \log_2(n) \rceil$$ returns the correct answer.

EDITED: As pointed out in the comments, the above does not return the correct answer for powers of 2. The correct answer is: $$\lfloor \log_2(n) \rfloor + 1$$

-
As @woz pointed out below, the counter-example is if $n = 2$, you need 2 miles, but your answer gives 1 mile as the answer. – Paresh Nov 27 '12 at 13:49
or any power of 2, for that matter. thanks. – anorton Nov 27 '12 at 13:52
And floor instead of ceiling :) – Paresh Nov 27 '12 at 13:58
Doh. Thanks for having patience... :) – anorton Nov 27 '12 at 14:00
Either $\lfloor\log_2(n)+1\rfloor$ or $\lceil\log_2(n+1)\rceil$ give the correct answer. Each jumps $1$ at each power of $2$. – robjohn Nov 27 '12 at 14:02

The correct answer is $\lceil \log_2(n+1)\rceil$.

-
 I can disprove this by counterexample. If you have 2 balls, you have to go 2 miles (2=>1=>0), and ⌈log2(2)⌉ = 1. Since, 1 != 2, this formula is incorrect. – woz Nov 27 '12 at 13:43 @woa You are right. Did the correction. – egens Nov 27 '12 at 13:48 This is correct, but could use some explanation. – robjohn♦ Nov 27 '12 at 13:59 @egens Isn't it log(n)+1 – The Programmer Nov 27 '12 at 14:17

For intergers my guess is $$\lfloor \log_2 n +1\rfloor$$

-
Hmm, this could really use some context. A bald answer is not likely to provide much insight.... – Simon Hayward Nov 27 '12 at 13:38
This is correct, but could use some explanation. – robjohn Nov 27 '12 at 13:59