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

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.


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

Tags:

Puzzle

Combinatorics

Sequences And Series

Recreational Mathematics

Related

Find the group with presentation $\langle x, y: xy=yx, x^5=y^3\rangle$. Why is the euler characteristic of a sphere 2? Why are higher/graduate level books discussing deep topics/results written if the author clearly doesn't want the reader to understand any of it? How to understand this polar coordinate transformation of ODE Prove that $\int_{0}^{\infty}\frac{(\arctan x)^3}{x^3}dx=\frac{3π}{2}\ln2-\frac{π^3}{16}$ Proving $\int_0^\infty\frac{\mathrm dw}{(n+w)(\pi^2+(\log w)^2)}=\frac1{\log n}-\frac1{n-1}$ for any positive integer $n\geq 2$ What is the derivative of $\log \det X$ when $X$ is symmetric? Combinations of elements from multiple sets with constraints Find minimum of piecewise defined function Spivak Calculus. Why is the books proof valid? Is my attempt at a proof valid? All functions such that $\lim_{n\to \infty} \int_n^{n+\frac 1n} f(x)dx$ is a non-zero finite value What is an example function of a transitive yet non-reflexive and non-symmetric relation?

Recent Posts