11
$\begingroup$

I have this question that I think it may be very interesting to all maths' lovers.

A cat caught $n$ (integer) mice and put them in line, numbered them from 1 to $n$, from left to right. He starts eating every other mouse, starting with the mouse at the 1st position, i.e. 1, 3, 5 ... (all mice at the odd positions will be gone). He then starts a new iteration, no matter if there is a surviving mouse at the end of the line, by going back to the left and eats every other mouse again, starting always with the first surviving mouse from the previous iteration.

Until there is one mouse left.

What is the position of the surviving mouse in the original sequence from 1 to n?

$\endgroup$
  • 1
    $\begingroup$ Hint: after the first time eating through the line, what are the numbers of the surviving mice? From there, using the original numbers, what mice survive round 2? Can you see a pattern? $\endgroup$ – Arthur Apr 5 '17 at 19:09
  • $\begingroup$ I can give two examples First example : n=7 From the sequence 1, 2, 3, 4, 5, 6, 7 1st iteration : 1, 3, 5, 7 will be gone, 2, 4, 6 remain 2nd iteration : 2, 6 will be gone Surviving mouse is the 4th. Second example : n=4 From the sequence 1, 2, 3, 4 1st iteration : 1, 3 will be gone, 2, 4 remain 2nd iteration : 2 will be gone Surviving mouse is the 4th $\endgroup$ – Jay Tee Apr 5 '17 at 19:13
  • 3
    $\begingroup$ Josephus Numbers - not quite the same since this is a line, but almost. $\endgroup$ – Paul Sinclair Apr 5 '17 at 23:13
7
$\begingroup$

One can use recursion to solve such questions. Let $a_{n}$ be the number of the last mouse surviving when there are $n$ to begin with.

  • If $n$ is odd, $n = 2k+1$, then after one round we are left with $k$ mice, $2, 4, \ldots, 2k$ and we do the same procedure. The mouse that is left is $2a_k$. Thus, $$ a_{2k+1} = 2a_k. $$

  • If $n$ is even, $n = 2k$, then after one round we are left with $k$ mice again, the same ones. Thus $$ a_{2k} = 2a_k. $$

It follows by induction that $$ a_n = 2^{\lfloor \log_2 n \rfloor}. $$

$\endgroup$
17
$\begingroup$

The other answers are correct, but let me offer an alternative way to see it. Suppose you had 7 mouses, for example. Number them in binary and go through the cat's iterations:

001 -> 001
010 -> 010 -> 010
011 -> 011
100 -> 100 -> 100
101 -> 101
110 -> 110 -> 110
111 -> 111

In the first round the cat eats all mice ending in 1, so that only the ones ending in 0 are left. On the second round the cat eats all mice ending in 10, so that only the ones ending in 00 are left. And so on. (Alternatively, you can drop one trailing zero from all mice after the first round and iterate with always eating mice ending in 1.)

That is, if a mouse has $k$ trailing zeroes, it will survive exactly $k$ rounds. The last survivor is the one with the largest amount of trailing zeroes.

The number of trailing zeroes in the set $\{1,\dots,n\}$ is always maximized by a power of two and the maximizer is unique. (Please ask if you want a proof for this statement. It might work as a separate question, too.) The largest power of two that does not exceed $n$ is indeed $a_n = 2^{\lfloor \log_2 n \rfloor}$ as others have pointed out.

$\endgroup$
7
$\begingroup$

If $n$ is even, then we have something like $[1, 2, 3, 4, 5, 6]$ becoming $[2, 4, 6]$, which is the same as playing a new game of size $n/2$ and multiplying the answer from $[1, 2, 3]$ by $2$.

If $n$ is odd, then we have something like $[1, 2, 3, 4, 5]$ becoming $[2, 4]$, which is the same as playing a new game of size $(n-1)/2$ and multiplying the answer from $[1, 2]$ by $2$.

We can simplify the two cases into one by saying $n$ becomes $\lfloor\frac{n}{2}\rfloor$ instead. Therefore:

$S(n) = 2S(\lfloor\frac{n}{2}\rfloor)$ where $S(1) = 1$

So $S(n) = 2^{\lfloor \log_2(n)\rfloor}$

This is also the same as finding the most significant bit of $n$ (i.e. the largest power of $2$ less than or equal to $n$). Write $n$ in binary and then set everything to $0$ except the leading bit.

$\endgroup$
7
$\begingroup$

Following Arthur's hint: after the $k$th round, the only mice that are left are the multiples of $2^{k+1}$. This is because in the $k$th round, the cat eats all the mice that are not divisible by $2^k$.

Let $2^k$ be the largest power of $2$ that is $\le n$, i.e. $k=\lfloor \log_2 n\rfloor$.

Then the last mouse is the largest mouse divisible by $2^k$, i.e. $m2^k$ where $m=\lfloor n/2^k\rfloor$.

So, the last mouse is $$m2^k = \lfloor n/2^k\rfloor 2^k = \lfloor 2^{\log_2 (n) - k}\rfloor 2^k = \lfloor 2^{\log_2 (n) - \lfloor \log_2 n\rfloor}\rfloor 2^{\lfloor \log_2 n\rfloor} = 2^{\lfloor \log_2 n\rfloor},$$ where we use the fact that $\log_2(n) - \lfloor \log_2 n \rfloor \in [0,1)$.

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