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

Проект МЦНМО
при участии
школы 57
Задача 105076
Темы:    [ Полуинварианты ]
[ Двоичная система счисления ]
[ Перестановки и подстановки (прочее) ]
[ Процессы и операции ]
[ Индукция (прочее) ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение 1

  Сопоставим каждой карте цифру: единицу, если она лежит рубашкой вверх, и двойку – если рубашкой вниз. Записав эти цифры слева направо, начиная с цифры, соответствующей верхней карте, мы получим некоторое натуральное число. При каждом переворачивании пачки карт это число уменьшается: двойка, соответствующая верхней карте в пачке, заменяется единицей, а цифры в более старших разрядах не меняются. Но натуральное число не может уменьшаться бесконечно, поэтому когда-нибудь переворачивания прекратятся. Это и значит, что все карты легли рубашкой вверх.


Решение 2

  Индукция по толщине колоды. База (колода из одной карты) очевидна.
  Шаг индукции. Пусть утверждение задачи доказано для колоды из n карт. Рассмотрим колоду из  n + 1  карты.
  Если верхняя карта лежит рубашкой вверх, то она в переворачиваниях не участвует, и фактически все действия Петя производит с колодой из n карт. По предположению индукции в конце концов все карты лягут рубашкой вверх.
  Пусть верхняя карта лежит рубашкой вниз. Как только Петя её задействует, наверху окажется карта рубашкой вверх, что приводит нас к уже разобранному случаю. Если же Петя упорно не будет её трогать, то, по предположению индукции, в некоторый момент все оставшиеся карты лягут рубашкой вверх. Теперь Пете придется перевернуть верхнюю карту, на чём процесс и закончится.

Замечания

5 баллов

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

олимпиада
Название Московская математическая олимпиада
год
Номер 63
Год 2000
вариант
Класс 8
задача
Номер 5
олимпиада
Название Турнир городов
Турнир
Дата 1999/2000
Номер 21
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 3

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

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