Puzzle: Dropping balls along the way

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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