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

Question

Math question:

Write all numbers between 1 and 128 in line. Then begin to delete the numbers in this way: delete number 1, leave 2, delete 3, leave 4 and so on. Go on to the end of the line and then begin to delete in the other direction from the first number not deleted, then leave the second and so on. Go on like this until there is only one number left. What is this number?

Now, I have an easy solution for this problem. The point is that I have read a different solution which seems cleaner and interesting but which I don't fully understand.

Here the solution which I do not understand:

Let $x_k$ be the last remaining number after proceeding as described with the numbers between $1$ and $2^k$. If you proceed with numbers between $1$ and $2^{k+1}$, after the first iteration remain only the $2^k$ even numbers, and the following $k$ iterations select the even number in position $x_k$ counting from the bottom ($x_k^{th}$ even number from the bottom). So we have $$ x_{k+1}=2(2^k-x_k+1)=2^{k+1}-2x_k+2 $$ Knowing that $x_0=1$, we can easily obtain $x_1$, $x_2$, ..., $x_7$. So $x_7=86$ is the solution.

Now my problem is how to motivate the step from $2^k$ to $2^{k+1}$. Any clue?

Answer 1

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*}

Answer 2

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

Answer 3

The binary representation method used elsewhere works more smoothly if we first subtract $1$ from each number so now they go from $0$ to $127$ -- better rendered as $0000000$ to $1111111$ base two. Now the bits in each place alternate between $0$ and $1$ with equal length blocks of identical bits in each place value (one-number blocks in the ones bit, two-number blocks in the twos bit, etc). This guarantees that all numbers removed in the first step have $0$ in the ones bit, those removed in the second step (in reverse order) have $1$ in the twos bit, all numbers removed in the third step have $0$ in the fours bit, and so on in this alternating fashion. The number with the surviving bits after seven deletions is $1010101_2$. Adding $1$ to restore the original sequence of numbers and translating back to base ten gives $86$ as the winner.