6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What base is 128 in? $\endgroup$ Aug 23, 2018 at 23:46
  • $\begingroup$ @DougSpoonwood: don't be silly. $\endgroup$
    – TonyK
    Aug 24, 2018 at 11:36
  • $\begingroup$ @TonyK Do you mean to suggest that this question has the same answer if the numeral 128 is in base nine and if the numeral 128 is in base ten? I certainly haven't checked that. At the very least, in base 9, 128 equals the sum of (nine squared), twice nine, and eight which is an odd number. If I understand dan_fulea's answer correctly, that implies that if 128 is a base nine numeral, then it has a different answer than the one that dan_fulea provided. But, I haven't checked for certain. $\endgroup$ Aug 24, 2018 at 19:20
  • $\begingroup$ It is obviously base 10, otherwise it could be every base greater than 128, but not 9. $\endgroup$
    – chess4ever
    Aug 24, 2018 at 19:30

3 Answers 3

9
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Very nice, but how does this show the derivation of the formula for $x_{k+1}$ asked for in the OP? $\endgroup$
    – Jens
    Aug 23, 2018 at 18:28
  • $\begingroup$ Yes, a good point. Let us use $y_k=x_k-1$, so that we have a regular pattern, $y_2=$01, $y_3=$101, $y_4=$0101, $y_5=$10101 and so on. The passage from $y_k$ to $y_{k+1}$ is as follows. Star with $y_k$. Reverse every digit, so pass to $(2^k-1)-y_k$. Then shift (times $2$) and put the $1$ in the end (plus one). This gives$$y_{k+1}=2((2^k-1)-y_k)+1\ .$$ The recursion is harder to understand than the pattern. Note: The problem would be a beautiful one, if it started with "Write all the numbers from $0$ to $127$ in a line..." (Of course, we can shift it in our mind.) $\endgroup$
    – dan_fulea
    Aug 23, 2018 at 18:52
  • $\begingroup$ I've upvoted this. However, one might point out that you used base two numerals like 10000000, while simultaneously assuming that '128' in the original question consists of a base ten numeral. $\endgroup$ Aug 24, 2018 at 19:21
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you, now it is clear, I was confusing the games with the iterations and thinking in terms of actual numbers instead of indexes (their position). $\endgroup$
    – chess4ever
    Aug 24, 2018 at 11:57
  • 1
    $\begingroup$ @chess4ever: You're welcome. Note that we are free to see it in both ways, since we can consider the ordered $2^{k+1}$-tuple $(1,2,3,\ldots,x_k,\ldots,2^{k+1})$ where $x_k$ is both, the number $x_k$ as well as the number at the $x_k$-th position due to the specific ordering. $\endgroup$ Aug 24, 2018 at 12:12
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .