Задача №17018

Все двузначные числа, не оканчивающиеся нулем, выписывают одно за другим так, что каждое следующее начинается с той же цифры, которой оканчивается предыдущее. Получается некоторое многозначное число.

а) Из всех многозначных чисел, которые можно получить таким образом, выбирают наименьшее. Какое двузначное число при его записи будет выписано семнадцатым?
б) Из всех многозначных чисел, которые можно получить таким образом, выбирают наибольшее. Найдите его 5 последних цифр.
в) Из всех многозначных чисел, которые можно получить таким образом, выбирают наименьшее и наибольшее. Найдите их сумму.

Решение. Двузначных чисел без нулей существует ровно $81=9\cdot 9\text{,}$ из которых требуется построить наибольшую цепочку.

Структура цепочки. Каждое следующее число начинается с той цифры, которой оканчивается предыдущее. Это эквивалентно эйлерову обходу полного орграфа на 9 вершинах (цифры 1–9), где петли соответствуют числам $11,22,\dots ,99\text{,}$ а остальные дуги — парам $(i;j)$ с $i\ne j\text{.}$ Можно показать, что максимальная длина цепочки равна 81 двузначному числу, что даёт $162$-значное число.

а) Наименьшее $162$-значное число. Самое маленькое число должно начинаться с $11\text{.}$ На каждом шаге выбираем наименьшее из ещё не использованных возможных следующих чисел. Тогда цепочка стартует так (точки разделяют двузначные числа):

$$\mathrm{11.12.21.13.31.14.41.15.51.16.61.17.71.18.81.19}$$

Следующее наименьшее возможное число — $91\text{,}$ но его ставить нельзя: процесс прервётся, так как закончатся числа, начинающиеся с $1\text{.}$ Поэтому ставим $92$ и далее:

$$\mathrm{92.22.23.32.24.42.25.52.26.62.27.72.28.82.29}$$

Затем число $91$ ставить нельзя, $92$ уже было — однозначно ставим $93\text{:}$

$$\mathrm{93.33.34.43.35.53.36.63.37.73.38.83.39}$$

И так далее. Закономерность очевидна. Несколько последних чисел в цепочке:

$$\dots \mathrm{97.77.78.87.79.98.88.89.99.91.}$$

Выпишем последовательность двузначных чисел в наименьшем варианте по порядку:

$$\underset{1}{\underbrace{11}},\underset{2}{\underbrace{12}},\underset{3}{\underbrace{21}},\underset{4}{\underbrace{13}},\underset{5}{\underbrace{31}},\underset{6}{\underbrace{14}},\underset{7}{\underbrace{41}},\underset{8}{\underbrace{15}},\underset{9}{\underbrace{51}},\underset{10}{\underbrace{16}},\underset{11}{\underbrace{61}},\underset{12}{\underbrace{17}},\underset{13}{\underbrace{71}},\underset{14}{\underbrace{18}},\underset{15}{\underbrace{81}},\underset{16}{\underbrace{19}},\underset{17}{\underbrace{92}},\dots$$

Семнадцатое двузначное число — 92.

б) Наибольшее $162$-значное число. Аналогично строится самое большое число: на каждом шаге выбираем наибольшее из возможных. Начало и конец:

Начало: $\mathrm{99.98.89.97.79.96.69.95.59.94.49.93.39.92.29.91}\dots$

Конец: $\dots \mathrm{13.33.32.23.31.12.22.21.11.19}\text{.}$

Последние пять цифр наибольшего числа — 11119.

в) Сумма наименьшего и наибольшего. Запишем оба $162$-значных числа в столбик и сложим:

\begin{array}{r} \displaystyle + \,\, 11122113311441155116611771188119 \ldots 9777788779988889991 \\ \displaystyle 99988997799669955994499339922991 \ldots 1333322331122221119 \\ \displaystyle \hline 11111111111111111111111111111111 \ldots 11111111111111111110 \end{array}

Каждый разряд (кроме самого младшего) даёт сумму $11\text{,}$ поэтому при сложении в столбик в каждом разряде получается цифра $1$ с переносом $1$ в следующий старший разряд, а самый младший разряд равен $9+1=10\text{,}$ то есть $0$ с переносом $1\text{.}$ В результате получается число, состоящее из $162$ единиц, за которыми следует ноль (всего $163$ цифры).

Ответ:

а) $92$

б) $11119$

в) $\underset{162}{\underbrace{111\dots 1}}0$