ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35664
Темы:    [ Четность и нечетность ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Подсказка

При выполнении каждой операции не меняется чётность каждой цифры.


Решение

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


Ответ

101010101.

Источники и прецеденты использования

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .