Question

Две соседние цифры в числе назовем неинтересной двойкой, если при их перестановке число не увеличивается. Найдите максимальное количество цифр, которое может быть в числе, если известно, что в нем есть только 3 неинтересных пары цифр

Answer 1

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

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

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

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

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

Answer 2

Для того чтобы максимизировать количество цифр в числе, при условии, что в нем есть только 3 неинтересные пары цифр, мы можем воспользоваться следующей стратегией:

Пусть первая неинтересная пара будет "21", вторая "43", и третья "65". Таким образом, мы получим число "214365". При перестановке любых соседних цифр, число не увеличится, так как наибольшая цифра уже стоит на первом месте, затем идут следующие по убыванию.

Итак, максимальное количество цифр, которое может быть в числе при условии, что в нем есть только 3 неинтересные пары цифр, равно 6, и это число "214365".