Erase every other number from $1, 2, 3, ... 2000$ until only one number left

Question

One writes $1, 2, 3, ... 2000$ on the blackboard.

We erase every other number from left, so after one iteration we are left with $2, 4, ... 2000$

Then we erase every other number from right..

We keep repeating to erase from left and right one after another, eventually there is only one number left.

What would be that number?

I wrote a program, unless there is a bug, the answer should be 982. But is there a way to mathematically induce the results, and generalize to arbitrary number (not just 2000?)

Following the suggestion, it seems like for power of 2, the answers go like this

$N=2$, final number is 2

$N=4$, final number is 2

$N=8$, final number is 6

$N=16$, final number is 6

$N=32$, final number is 22

$N=64$, final number is 22

$N=128$, final number is 86

$N=256$, final number is 86

The answer will jump to 4 times previous answer minus 2, for every time we multiply $N$ by 4...

Answer 1

Here's a step, at least, toward a solution.

Let $S(N)$ denote the "surviving" number as a function of $N$. Now after the first pass from left to right, only the even numbers from $2$ up to $2\lfloor N/2\rfloor$ remain. Thus $S(N)$ satisfies the recursion

$$S(N)=2(\lfloor N/2\rfloor+1-S(\lfloor N/2\rfloor))$$

with $S(1)=1$ (i.e., once only one person, that person survives). Let's see first how this works for a power of $2$:

$$\begin{align} S(32)&=2(17-S(16))\\ &=34-4(9-S(8))\\ &=-2+8(5-S(4))\\ &=38-16(3-S(2))\\ &=-10+32(2-S(1))\\ &=54-32\\ &=22 \end{align}$$

Now let's look at $N=2000$:

$$\begin{align} S(2000)&=2(1001-S(1000))\\ &=2002-4(501-S(500))\\ &=-2+8(251-S(250))\\ &=2006-16(126-S(125))\\ &=-10+32(63-S(62))\\ &=2006-64(32-S(31))\\ &=-42+128(16-S(15))\\ &=2006-256(8-S(7))\\ &=-42+512(4-S(3))\\ &=2006-1024(2-S(1))\\ &=2006-1024\\ &=982 \end{align}$$

as the OP found. Whether the recursive formula can be simplified to an explicit closed formula I'll leave to someone else.

Answer 2

Here is the complete solution, using the excellent recurrence of Barry Cipra.

Consider the $k$-bit-long binary representation of $N = b_1 b_2 b_3 \dots b_k$ where $b_1$ is the most significant bit.

For convenience define $B_j = b_1 b_2 \dots b_j = \lfloor N / 2^{k-j}\rfloor$, i.e. the number formed by the most significant $j$ bits. Note that $B_k = N$ and $B_1 = b_1 = 1$.

Next we "unwind" the recurrence a bit:

$$ \begin{align} S(N) = S(B_k) &= 2(B_{k-1} + 1 - S(B_{k-1}))\\ &=2(B_{k-1} + 1) - 2 [ 2(B_{k-2} + 1 - S(B_{k-2}) ] \\ &=2(B_{k-1} + 1) - 4(B_{k-2} + 1) + 4 S(B_{k-2}) \end{align} $$

A nice thing now happens: if I may abuse notation a bit and mix up numbers with their binary representations (in red),

$$2B_{k-1} - 4B_{k-2} = \color{red}{b_1 b_2 \dots b_{k-2} b_{k-1} 0 - b_1 b_2 \dots b_{k-2} 0 0 = b_{k-1}0} = 2b_{k-1}$$

where the binary representations (in red) have some appended $0$s at the end to represent multiplication by $2$ or $4$. So now we can unwind faster:

$$ \begin{align} S(B_k) &= 2(b_{k-1} -1) + 4S(B_{k-2}) \\ &=2(b_{k-1} -1) + 4[2(b_{k-3} - 1) + 4 S(B_{k-4})]\\ &=2(b_{k-1} -1) + 8(b_{k-3} - 1) + 2^4 S(B_{k-4})\\ &=2(b_{k-1} -1) + 8(b_{k-3} - 1) + 32(b_{k-5}-1) + \dots \end{align} $$

Note that the subscript $j$ of the remaining $S(B_j)$ term decreases by $2$ for each unwinding step. So what happens at the end of all the unwinding can be case-analyzed:

For odd $k$: the last remaining term will be $S(B_1) = S(b_1) = S(b_1) = b_1 = 1$:

$$S(B_k) = \sum_{j = 1, 3, 5...} 2^j (b_{k-j} - 1) + 2^{k-1} S(B_1) = \sum_{j = 1, 3, 5...} 2^j (b_{k-j} - 1) + 2^{k-1} b_1$$

Interpretation: Based on the way I number the bits, $2^j b_{k-j}$ is the $b_{k-j}$ bit evaluated at its correct place-position. So the formula is equivalent to this recipe:

Recipe: Take the most significant bit's place-value (blue), and consider the $2$nd, $4$th, $6$th, etc least significant bits (red), i.e. the bits for place-values $2^1, 2^3, 2^5,$ etc. If a bit is $0$, then subtract its place-value.

E.g. $2000 = 11111010000 = \color{blue}{1}\color{red}{1}1\color{red}{1}1\color{red}{0}1\color{red}{0}0\color{red}{0}0 \implies S(2000) = 1024 - 2 - 8 - 32 = 982$

E.g. $64 = 1000000 = \color{blue}{1}\color{red}{0}0\color{red}{0}0\color{red}{0}0 \implies S(64) = 64 - 2 - 8 - 32 = 22$

For even $k$: the last remaining term will be $S(B_2)$. Luckily, $B_2 \in \{2, 3\}$ and in both cases $S(B_2) = S(2) = S(3) = 2$.

$$S(B_k) = \sum_{j = 1, 3, 5...} 2^j (b_{k-j} - 1) + 2^{k-2} S(B_2) = \sum_{j = 1, 3, 5...} 2^j (b_{k-j} - 1) + 2^{k-1} b_1$$

So surprisingly, the same recipe works! The only clarification is that since the most significant bit is also an even-numbered least-significant bit (because $k$ is even), it must not be included in the subtraction.

E.g. $32 = 100000 = \color{blue}{1}0\color{red}{0}0\color{red}{0}0 \implies S(32) = 32 - 2 - 8 = 22$

Further remarks:

• It is curious that only half the bits matter. E.g. the recipe immediately shows $S(8) = S(1000_2) = S(13) = S(1101_2)$.

• Barry's recurrence is already $\log(N)$ time, so my recipe is not faster. However, it does give an explicit summation.

• The explicit summation, especially in the form of the recipe, allows easy proofs of the OP's observation that $S(2^k)$ values come in pairs, and $S(2^{k+2}) = 4S(2^k) - 2$.