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

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

Условие

В колоде 16 карт, пронумерованных сверху вниз. Разрешается снять часть колоды сверху, после чего снятую и оставшуюся части колоды, не переворачивая "врезать" друг в друга. Может ли случиться, что после нескольких таких операций карты окажутся пронумерованными снизу вверх? Если да, то за какое наименьшее число операций это может произойти?


Решение

  Приведём способ, позволяющий добиться требуемого порядка за четыре операции. Каждый раз будем снимать ровно половину колоды – 8 карт сверху и "врезать" снятую часть колоды в оставшуюся "через одну". Трансформация колоды при таких операциях показана на схеме:

  Рассмотрим произвольные три операции над колодой, удовлетворяющие условию. При каждой операции колода делится на две части: часть, которая снимается, и часть, которая остается. Поскольку всего карт 16, то одна из этих частей содержит не менее восьми карт. Аналогичное рассуждение показывает, что среди этих карт найдутся по крайней мере четыре, которые при второй операции либо все были в снятой части колоды, либо все в оставшейся. А среди них, в свою очередь, найдутся две карты, оказавшиеся в одной части и при третьей операции. Таким образом, мы нашли две карты, которые при всех операциях либо снимались, либо оставались в колоде вместе. Тем самым порядок этих карт в колоде после трех операций не изменился. Значит, за три операции нумерация карт в колоде поменяться на противоположную не может.

Замечания

Источник решения: книга В.О. Бугаенко "Турниры им. Ломоносова. Конкурсы по математике". МЦНМО-ЧеРо. 1998.

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

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 02
Дата 1979
задача
Номер 03

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

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