Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука | Задачи
 Написать комментарий  Добавить новое сообщение
перестановки цифр с уменьшением
9.01.2002 19:09 | МЦНМО

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


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


    Написать комментарий
     Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования