Задача 78171
|
|
 |
Условие
Можно ли расположить все трёхзначные числа, не оканчивающиеся нулями, в последовательности так, чтобы последняя цифра каждого числа была равна первой цифре следующего за ним?
Решение
Рассмотрим полный граф с девятью вершинами, занумерованных цифрами от 1 до 9. Каждому трёхзначному числу вида abc (где a ≠ c), не оканчивающемуся на ноль, сопоставим ребро, соединяющее вершины с номерами a и c. Согласно задаче 30806 в графе существует эйлеров цикл. Пройдя этот цикл десять раз (для b = 0, 1, ..., 9) в одном направлении и десять раз – в другом, получим искомую последовательность без чисел вида aba. Но вставить эти числа в последовательность уже нетрудно.
Ответ
Можно.
