При каком наименьшем n>1 можно расставить все натуральные числа от 1 до n по кругу так, чтобы любые два соседних числа имели в своей записи одинаковую цифру

Для решения этой задачи нужно найти наименьшее $n > 1$, для которого возможно расположить числа $1, 2, \dots, n$ по кругу таким образом, чтобы любые два соседних числа имели хотя бы одну общую цифру в записи.

Алгоритм рассуждения:

1. Определение условия: Каждое число $a$ и следующее за ним $b$ должны иметь хотя бы одну общую цифру. Например, числа $12$ и $23$ можно считать соседними, так как цифра $2$ присутствует в обеих записях.

2. Попытка построения последовательности: Построение последовательности вручную для малых $n$, проверяя выполнение условия для каждой пары соседних чисел. Обратите внимание, что числа должны быть расставлены по кругу, то есть $n$ соединяется с $1$.

3. Минимизация $n$: Для поиска наименьшего $n$ необходимо перебрать последовательности, начиная с $n = 2$, и проверять, возможно ли удовлетворить условие.

Проверка:

$n = 2$:

Числа $1$ и $2$. Между ними нет общей цифры. Условие невыполнимо.

$n = 3$:

Числа $1, 2, 3$. Ни одна из пар ($1$ и $2$, $2$ и $3$, $3$ и $1$) не имеет общей цифры. Условие невыполнимо.

$n = 4$:

Числа $1, 2, 3, 4$. Между любой парой соседних чисел также нет общей цифры. Условие невыполнимо.

$n = 13$:

Если взять числа $1$ до $13$, можно построить следующую последовательность:

• $1 \to 12 \to 23 \to 34 \to 45 \to 56 \to 67 \to 78 \to 89 \to 91$