Question

На доске записано число 123456789. У написанного числа выбираются две соседние ненулевые цифры, из каждой из них вычитается по единице, после этого выбранные цифры меняются местами. Какое наименьшее число может быть получено в результате таких операций?

Answer 1

 Заметим, что при выполнении каждой операции не меняется четность цифры, стоящей на каждом месте. В самом деле, вначале у нас было число 123456789, т.е. число вида НЧНЧНЧНЧН (Н означает нечетную цифру, а Ч - четную). Если мы возьмем пару соседних цифр, скажем НЧ, то при уменьшении этих цифр на 1 получится пара ЧН, а при смене местами снова получится пара НЧ. Аналогично, если мы возьмем пару соседних цифр вида ЧН, то при уменьшении этих цифр на 1 получится пара НЧ, а при смене местами снова получится пара ЧН. Итак, в процессе выполнения операций число все время будет иметь вид НЧНЧНЧНЧН. Минимальным числом такого вида, очевидно, является число 101010101. Осталось показать, что число 101010101 получить можно. Для этого достаточно в исходном числе 123456789 применить 2 раза нашу операцию к паре соседних цифр 2 и 3, применить 4 раза операцию к паре соседних цифр 4 и 5, 6 раз операцию к паре соседних цифр 6 и 7, и наконец 8 раз операцию к паре соседних цифр 8 и 9.     101010101.00