5
$\begingroup$

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.

  • 1
    Try it first for 16 and 32 balls. What happens with a number of balls between 16 and 32?2012-11-27
  • 0
    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.2012-11-27
  • 1
    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.2012-11-27
  • 0
    @Paresh That would also match the example, where 3 of 5 balls are lost.2012-11-27
  • 0
    @Paresh Thank you for the suggestion Paresh2012-11-27
  • 0
    If you consider the problem in binary, it's simply the number of digits in the binary representation of n. Joel Cohen gives a good explanation below.2012-11-27

5 Answers 5

12

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.

6

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

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

  • 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.2012-11-27
  • 0
    or any power of 2, for that matter. thanks.2012-11-27
  • 1
    And floor instead of ceiling :)2012-11-27
  • 0
    Doh. Thanks for having patience... :)2012-11-27
  • 0
    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$.2012-11-27
1

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

  • 0
    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.2012-11-27
  • 0
    @woa You are right. Did the correction.2012-11-27
  • 0
    This is correct, but could use some explanation.2012-11-27
  • 0
    @egens Isn't it log(n)+12012-11-27
0

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

  • 5
    Hmm, this could really use some context. A bald answer is not likely to provide much insight....2012-11-27
  • 0
    This is correct, but could use some explanation.2012-11-27