Задача 8.2. На доске написано 432105. За одно действие разрешается либо поменять местами две соседние цифры в этой записи, либо заменить число, образованное двумя соседними цифрами, на число на 9 меньше, если оно неотрицательное. При этом в записи могут появиться нули в начале. (а) Запись какого наименьшего числа можно получить (возможно, с нулями в начале)? (б) Запись какого наибольшего числа можно получить (возможно, с нулями в начале)?

Уменьшение пары цифр на 9 не меняет сумму её цифр по модулю 9; перестановка соседних цифр также не меняет сумму всех цифр. Поэтому у любой достижимой записи сумма цифр сравнима с 15 по модулю 9. Однако этого условия недостаточно, чтобы установить достижимость конкретной записи: нужно также проверить, существует ли последовательность разрешённых действий, ведущая к ней.

Чтобы найти точные минимум и максимум, требуется перебрать граф достижимых записей из 432105: из каждой записи добавить все результаты допустимых перестановок соседних цифр и всех допустимых замен соседней пары на пару, значение которой на 9 меньше. На изображении нет результатов такого перебора, а без его выполнения точные экстремумы нельзя достоверно назвать.

Например, первым ходом можно получить записи 342105, 423105, 431205 и 432015 заменой допустимой соседней пары; также можно переставлять соседние цифры. Эти примеры сами по себе не определяют наименьшее и наибольшее достижимые числа.

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