alternate deletion of integers between 1 and 128, which is the last one?

Let us do the steps here explicitly. Since i will use computer aid, i will do the job in its language writing the numbers in binary representation. The initial list is:

  1 ~ 00000001
  2 ~ 00000010
  3 ~ 00000011
  4 ~ 00000100
  5 ~ 00000101
  6 ~ 00000110
  7 ~ 00000111
  8 ~ 00001000
  9 ~ 00001001
::::::::::::::: many other numbers
119 ~ 01110111
120 ~ 01111000
121 ~ 01111001
122 ~ 01111010
123 ~ 01111011
124 ~ 01111100
125 ~ 01111101
126 ~ 01111110
127 ~ 01111111
128 ~ 10000000

The last digit is $1,0,1,0,1,0,$... After the first deletion operation there is no number left ending in $1$, exactly those numbers remain that end in $0$. Let us write them explicitly.

  2 ~ 00000010
  4 ~ 00000100
  6 ~ 00000110
  8 ~ 00001000
::::::::::::::: many other numbers
120 ~ 01111000
122 ~ 01111010
124 ~ 01111100
126 ~ 01111110
128 ~ 10000000

OK. Now we start from the end. The last digit is a zero. We forget about it. The forelast is, starting from the end, $0,1,0,1,0,1,\dots$ and so on. We delete all of those numbers having a forelast zero. The list is thus after the second step

  2 ~ 00000010
  6 ~ 00000110
::::::::::::::: many other numbers
122 ~ 01111010
126 ~ 01111110

And there are only numbers ending in 10 remained. We forget about the 10 and restart the procedure. We delete the first number in the list, it has the pattern *010, so we remove all numbers with this pattern. There remain only numbers having the pattern *110. So note the asymmetry. At the first forth-and-back deletion operation the first number ended in one. Now it is a zero at the position that counts. The remained numbers are thus

  6 ~ (0)0000110
::::::::::::::: many other numbers
126 ~ (0)1111110

Now the pattern for the first number, and for the last number is "the same", only zeros, resp. only ones to be deleted on the position that gives the signal. We repeat and complete:

• After 1.st deletion $\to$ we remain with pattern *0.
• After 2.nd deletion $\leftarrow$ we remain with pattern *10.
• After 3.rd deletion $\to$ we remain with pattern *1 10.
• After 4.th deletion $\leftarrow$ we remain with pattern *01 10. From now on the forth-and-back deletions replace * by *01 by the same argument. So...
• After 5.th deletion $\to$ we remain with pattern *1 01 10.
• After 6.th deletion $\leftarrow$ we remain with pattern *01 01 10.
• After 7.th deletion $\to$ we remain with pattern *1 01 01 10.

There is only one number of this shape in the list, it is

01 01 01 10

And this winner is 01 01 01 10${}_2$, which is decimal $2+4+16+64 = 20+66=86$.

The recurrence relation \begin{align*} x_{k+1}&=\color{blue}{2}(2^k-x_k+1)\qquad\qquad\qquad (k\geq 0)\tag{1}\\ x_0&=1 \end{align*} can be derived by considering two different situations.

First game: $1,2,\ldots,2^k$:

• In this game we start with the numbers $1,2,\ldots 2^k$. We play the game till we find after $k$ steps the element $x_k\in\{1,2,\ldots,2^k\}$.

We can now relate the solution $x_k$ from the first game with the solution $x_{k+1}$ in a game consisting of the numbers $1,2,\ldots,2^{k+1}$.

Second game: $1,2,\ldots,2^{k+1}$:

• The first step is to eliminate all odd numbers, leaving $2^k$ numbers $2,4,\ldots,2^{k+1}$.

• Now we are in a situation very similar to the first game. We have $2^k$ numbers, but there are two differences. Each element is doubled in size and we start from the other side with element $2^{k+1}=2\cdot 2^k$ since this is the second step in this game.

  • We have $2^k$ numbers, namely $2,4,6,\ldots,2^{k+1}$, each number twice as big as in the first game. This explains the factor $\color{blue}{2}$ in (1) marked in blue.

  • The position $x_k$ which was derived in the first game when starting from $1$ has to be exchanged with $2^k-x_k+1$ which is the corresponding position when starting from the other side.

This explains the recurrence relation (1) giving: \begin{align*} (x_k)_{k\geq 0}=(1,2,2,6,6,22,22,\color{blue}{86},86,342,342,\ldots) \end{align*}