Задача 32012

Темы:    [ Теория алгоритмов (прочее) ] [ Двоичная система счисления ] [ Принцип Дирихле (прочее) ] [ Оценка + пример ]

Сложность: 4 Классы: 7,8,9

Условие

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

Решение

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

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

Замечания

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

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

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