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