Эйлеровы графы

Рассмотрим граф, вершинами которого являются пары цифр (упорядоченные). Количество таких пар (каждое из 2 чисел можно выбрать 10 способами). Будем проводить стрелочку из вершины в вершину , если второе число равно первому числу . Заметим, что из каждой вершины выходит 10 ребер и входит 10 ребер. Если мы сотрем ориентацию на ребрах, то легко видеть, что полученный граф будет связным. Тогда также как и во второй задаче найдем ориентированный цикл, содержащий все ребра. Заметим, что каждой последовательности из 3 чисел соответствует ровно 1 ребро (между первыми двумя числами и последними двумя числами). Выпишем сначала произвольную пару чисел, а затем будем дописывать следующую согласно нашему циклу (то есть, если мы выписали числа из вершины , а следующей в нашем цикле является вершина , то допишем на доску последнюю цифру и так далее). Поскольку мы прошли по всем ребрам ровно 1 раз, у нас встретятся все комбинации из 3 чисел, причем ровно по 1 разу, что и требовалось.