Around a circle, the natural numbers from 1 to $N$ with $N>2$ are written, each exactly once, in such a way that two neighbors have at least one digit in common. Find the smallest $N>2$ for which this is possible.

#
Solution

Since 3 will appear, we should use 13 and 23. Thus, as $9<23$, 9 must be in the circle. Its two neighbors must contain the digit 9, the smallest would be 19 and 29, consequently $N$ must be at least 29. Now, to prove that 29 is the minimum, it suffices to construct an example:

$$
1,12,2,22,20,21,23,3,13,14,4,24,25,5,15,10,11,19,9,29,28,8,18,17,7,27,26,6,16
$$