Determine the number of ten-digit positive integers with the following properties: $\bullet$ Each of the digits $0, 1, 2, . . . , 8$ and $9$ is contained exactly once. $\bullet$ Each digit, except $9$, has a neighbouring digit that is larger than it. (Note. For example, in the number $1230$, the digits $1$ and $3$ are the neighbouring digits of $2$ while $2$ and $0$ are the neighbouring digits of $3$. The digits $1$ and $0$ have only one neighbouring digit.) (Karl Czakler)
Problem
Source: 2022 Austrian Regional Competition For Advanced Students p2
Tags: combinatorics, Digits
05.10.2022 20:57
Let be $\overline{a_1a_2...a_9a_{10}}$ a ten-digit number with the given conditions. We define a $k-block$ a sequence of $k$ consecutive digits of the given number: $\overline{a_pa_{p+1}...a_{p+k-1}}$, where $2\le k\le 9;\;1\le p\le 11-k$. The digit $8$ must be neighbour of $9$. Results: the digits $8$ and $9$ form a $2-block$ in any order, hence exist $2$ possible pairs (89 and 98). The digit $7$ must have one of the digits $8$ or $9$ as neighbour, hence $7$ must be neighbour of a $2-block$ containing $8$ and $9$. For each $2-block$, the digit $7$ can be placed left or right. Conclusion: the digits $7,8,9$ form a $3-block$ and exist $2\cdot2=2^2$ possible such $3-blocks$. For $m\in\{7,6,...,2,1\}$, in this order, results successively: Exist $2^{8-m}$ possible $(9-m)-blocks$ containing the digits $9,8,...,m+1$. The digit $m$ must be neighbour of $m+1,m+2,...$ or $9$. Results: the digit $m$ must be neighbour of a $(9-m)-block$ containing the digits $m+1,m+2,...,9$. For each $(9-m)-block$, the digit $m$ can be placed left or right. Conclusion: the digits $m,m+1,...,9$ form a $(10-m)-block$ and exist $2\cdot2^{8-m}=2^{9-m}$ possible such $(10-m)-blocks$. For $m=1$ results: the possible number of $9-blocks$ containing the digits $1,2,...,8,9$ is $2^8=256$. The digit $0$ can be placed only right to a $9-block$ containing the digits $1,2,...,8,9$ (the ten-digit number cannot begin with $0$). Conclusion: exist $256$ possible ten-digit numbers with the requested conditions.
24.10.2022 22:02
Since the solution was carefully written, I decided that I had misunderstood the problem.