Предположим, что нашлось число с максимальным количеством цифр. Добавим ему в начало "0". Так как число не может начинаться с нуля, первая цифра больше нуля, потому новая неинтересная пара не образуется. Найдём максимальное количество цифр в таком числе, а потом отнимем 1 и получим ответ.

Предположим, что в таком числе идут 10 интересных пар цифр подряд. Тогда каждая следующая цифра больше предыдущей хотя бы на 1, так как при перемене их местами число увеличивается. Получается, последняя цифра больше первой на 10, но такого быть не может. Противоречие. Тогда в полученном числе не могут идти 10 интересных пар цифр подряд.

Пусть в числе хотя бы 41 цифра. Тогда в нём 40 пар цифр. Разобьём его на 4 группы по 10 подряд идущих пар. В каждой из них должна быть неинтересная пара цифр, но тогда их не менее четырёх. Противоречие. Тогда в числе не более 40 цифр. Уберём 0 в начале - получим 39 цифр.

Пример такого числа: 1234567890123... (Дальше дописывать не буду. Число оканчивается, когда в нём в четвёртый раз появляется цифра "9".)

Ответ: 39 цифр.