up vote 6 down vote favorite
1

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?

share|cite|improve this question
1  
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? – Arthur 14 hours ago
    
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 – Jay Tee 14 hours ago
    
Josephus Numbers - not quite the same since this is a line, but almost. – Paul Sinclair 10 hours ago
up vote 4 down vote accepted

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

share|cite|improve this answer
up vote 9 down vote

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.

share|cite|improve this answer
up vote 6 down vote

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

share|cite|improve this answer
up vote 5 down vote

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.