Estonian Mathematical Olympiad

Assume that for some $n$, a suitable ordering exists. From condition 2 we see that the sums of digits of any two consecutive numbers differ by exactly 1, and thus have opposite parities. As the first number has an even sum of digits, the $10^n$-th number must have an odd sum of digits. As the latter sum is $9n$, this means that the conditions can only be satisfied for odd $n$.

Now let $n$ be odd. We prove by induction that a suitable ordering exists. For $n=1$, the natural ordering works. Now let $n>1$ and assume that an ordering exists for $n-2$. We first order all numbers starting with 00, using the existing ordering for the other digits. Then we order the numbers starting with 01 in the reverse existing ordering for the other digits, then the numbers starting with 02 in the original order, and so on. During this process, we change the first two digits in the following order: \begin{array}{r@{\quad}l} 00 & \rightarrow 01 \rightarrow \dots \rightarrow 09 \rightarrow 19 \rightarrow 18 \rightarrow \dots \rightarrow 10 \rightarrow \\ & \rightarrow 20 \rightarrow 21 \rightarrow \dots \rightarrow 29 \rightarrow 39 \rightarrow 38 \rightarrow \dots \rightarrow 30 \rightarrow \\ & \rightarrow 40 \rightarrow 41 \rightarrow \dots \rightarrow 49 \rightarrow 59 \rightarrow 58 \rightarrow \dots \rightarrow 50 \rightarrow \\ & \rightarrow 60 \rightarrow 61 \rightarrow \dots \rightarrow 69 \rightarrow 79 \rightarrow 78 \rightarrow \dots \rightarrow 70 \rightarrow \\ & \rightarrow 80 \rightarrow 81 \rightarrow \dots \rightarrow 89. \end{array}

The last number written so far ends with zeros. It remains to order the numbers starting with a 9. We divide them into groups based on their last $n-2$ digits. We order these groups by the ordering existing for numbers with $n-2$ digits. Within the first group, we order the numbers in the descending order, within the second group in the ascending order etc. There are an even number of groups, so the final group is in the ascending order. Thus the created ordering will satisfy the conditions of the problem.

---

Alternative solution.

We exclude the even $n$ like in Solution 1. Like in Solution 1, we find an ordering for odd $n$ by induction. We again divide the numbers into groups based on their last $n-2$ digits and order the groups by the existing ordering. There are again an even number of groups.

In odd-numbered groups, we order the numbers in the group based on their first two digits, using the ordering in Fig. 42, starting from 00 and ending with 54. In even-numbered groups, we use the same ordering backwards, except for the final group, where we use the ordering in Fig. 43, starting with 54 and ending with 99.



Fig. 42 Fig. 43