Гуляем по графу

Оценка. Предположим, что число хотя бы -значное. Пронумеруем места, на которых стоят цифры, слева направо по возрастанию. Рассмотрим граф, вершинами которого будут места, на которых стоят цифры, а две вершины соединены направленным ребром если число на первом месте меньше, чем на втором. Тогда у нас образуется цикл и получается, что число на первом месте больше самого себя. Значит, число не более, чем -значное. Рассмотрев все тот же граф, получаем путь поэтому цифры на этих местах не больше и соответственно. Отсюда следует и пример