Consider the number obtained by writing the numbers $1,2,\ldots,1990$ one after another. In this number every digit on an even position is omitted; in the so obtained number, every digit on an odd position is omitted; then in the new number every digit on an even position is omitted, and so on. What will be the last remaining digit?
Problem
Source: Bulgaria 1990 P1
Tags: combinatorics
kred9
09.06.2021 21:09
The initial number has $1*9 + 2*90 + 3*900 + 4*991 = 6853$ total digits. Call this number $\overline{A_1A_2A_3A_4\dots A_{6853}}$. After the first step, we get $\overline{A_1A_3A_5\dots A_{6853}}$, where only odd numbers remain. After the second step, we get $\overline{A_3A_7A_{11}\dots A_{6851}}$, where only $3 \pmod{4}$ numbers are left. After the third step, only $3 \pmod{8}$ numbers are left, so $\overline{A_3A_{11}A_{19} \dots A_{6851}}$. After the fourth, only $11 \pmod{16}$ numbers are left, so $\overline{A_{11}A_{27}A_{43}\dots A_{6843}}$. After $5$ steps, only $11 \pmod{32}$ remain. After $6$, only $43 \pmod{64}$ remain. After $7$, only $43 \pmod{128}$ remain. After $8$, only $171 \pmod{256}$ remain. After $9$, only $171 \pmod{512}$ remain. After $10$, only $683 \pmod{1024}$ remain. After $11$, only $683 \pmod{2048}$ remain. After $12$, only $2731 \pmod{4096}$ remain. Finally, after the $13$th step, only $2731 \pmod{8192}$ numbers remain. This is only $A_{2731}$, so we need to find the $2731$st digit initially written on the board. We have $1*9 + 2*90 + 3*847 +1 = 2731$, so the $2731$st digit written is the first digit of the $847$th $3$ digit number. The $847$th $3$ digit number is $946$, so the answer is $9$.