Все двузначные числа, не оканчивающиеся нулем, выписывают одно за другим так, что каждое следующее начинается с той же цифры, которой оканчивается предыдущее. Получается некоторое многозначное число.
а) Из всех многозначных чисел, которые можно получить таким образом, выбирают наименьшее. Какое двузначное число при его записи будет выписано семнадцатым?
б) Из всех многозначных чисел, которые можно получить таким образом, выбирают наибольшее. Найдите его 5 последних цифр.
в) Из всех многозначных чисел, которые можно получить таким образом, выбирают наименьшее и наибольшее. Найдите их сумму.
Пошаговый разбор и решение:
Заметим, что во всех числах будет ровно по $2 \cdot 81 = 162$ цифры, поэтому сравнивать их нужно будет поразрядно — то, какое число больше, полностью определяется тем, какая цифра больше в первом различающемся разряде.
Рассмотрим граф, вершины которого — числа от 1 до 9, и каждые две вершины соединены двумя ориентированными ребрами, соответствующими числам с такими цифрами. Кроме того, каждая вершина соединена петлей сама с собой — эти петли соответствуют числам с одинаковыми цифрами. Из каждой вершины исходит 8 стрелочек и входит тоже 8 стрелочек (не считая петли). В таком графе есть путь, проходящий по всем стрелочкам ровно по одному разу, то есть такое число действительно существует. Это верно и для любого другого связного графа, в котором для всех вершин поровну входящих и исходящих стрелочек.
а) Для наименьшего числа нужно каждый раз выбирать наименьшее из возможных чисел. Тогда начало будет выглядеть так $11, 12, 21, 13, 31, \ldots 19, \ldots$ причем сейчас нельзя выбрать число 91: все числа, начинающиеся на 1, уже использованы, поэтому семнадцатым будет выписано число 92.
б) Для наибольшего числа наоборот нужно каждый раз выбирать наибольшее из возможных чисел. Поэтому число будет выглядеть так:
$99, 98, 89, 97, 79, \ldots, 91, 18, 88, 87, 78, 86, 68, \ldots 81, 17, 77, \ldots$
Отсюда понятна закономерность — число разбивается на блоки, в каждом из которых используются все числа с вхождением сначала девятки, потом восьмерки и так далее. Конец числа будет выглядеть как $33, 32, 23, 31, 12, 22, 21, 11, 19$ Значит, последние 5 цифр это 11 119.
в) Если в двух числах заменить каждую цифру на ее дополнение до 10, знак неравенства между числами изменится на противоположный: в первом различающемся разряде если были цифры $x меньше y$ то $10 - x больше 10 - y$ Значит, при такой замене самое большое число превратится в самое маленькое. Поэтому их сумма будет равна $111 \ldots 110$ (при сложении в столбик в каждом разряде будет получаться 10 и еще один — переносом из предыдущего разряда), где единиц ровно 162 штуки.
Ответ: а) 92; б) 11119; в) $111\ldots 110$
Правильный ответ: а) 92; б) 11119; в) $111\ldots 110$