Задача 105212

Темы:    [ Теория алгоритмов (прочее) ] [ Индукция (прочее) ] [ Процессы и операции ]

Сложность: 5 Классы: 9,10,11

Условие

В коробке лежат карточки, занумерованные натуральными числами от 1 до 2006. На карточке с номером 2006 лежит карточка с номером 2005 и т. д. до 1. За ход разрешается взять одну верхнюю карточку (из любой коробки) и переложить ее либо на дно пустой коробки, либо на карточку с номером на единицу больше. Сколько пустых коробок нужно для того, чтобы переложить все карточки в другую коробку?

Решение

Ответ следует из общего факта: пусть количество карточек равно n, где 2^{k - 1}n < 2^k (n, k --натуральные числа); тогда требуется k пустых коробок. Сначала покажем следующее: k коробок достаточно, причем если n = 2^{k - 1}, то не требуется использовать исходную коробку после того, как она освободится. При k = 1 утверждение тривиально. Пусть оно верно для некоторого натурального k.

Вначале пусть n = 2^k. Возьмем пустые коробки с номерами от 1 до k + 1. По предположению индукции можно перенести верхние 2^{k - 1} карточек в коробку номер k, используя коробки 1,..., k и не используя исходную коробку, которая еще не пуста. Аналогично переносим нижние 2^{k - 1} карточек в коробку номер k + 1, используя коробки 1,..., k - 1, k + 1. После этого подвергаем верхние карточки обратному перекладыванию, заменив исходную коробку на (k + 1)-ю. В итоге все карточки будут переложены в коробку k + 1, причем мы не использовали исходную коробку после того, как она освободилась.

Пусть теперь 2^k < n < 2^{k + 1}. Вначале переложим, как описано выше, 2^k карточек в коробку k + 1, использовав коробки 1,..., k + 1. Оставшиеся n - 2^k < 2^k карточек по предположению индукции можно переложить в коробку k, использовав коробки 1,..., k. Теперь подвергнем «верхние» карточки обратному перекладыванию, заменив исходную коробку на k-ю.

Для дальнейшего заметим, что если используется минимально возможное количество коробок, то все они окажутся одновременно занятыми не позже, чем мы освободим исходную коробку. Действительно, пусть это неверно. Отметим в начальный момент какую-то пустую коробку i. Пусть на некотором шаге мы кладем в нее карточку. Так как по предположению какая-то коробка будет после этого пуста, то можно заменить i на эту коробку начиная с данного шага. Будем поступать так каждый раз, когда нужно класть карточку в коробку i. В итоге мы переложим нижнюю карточку в некоторую коробку j. После этого повторим все действия в обратном порядке, заменив исходную коробку на j. Карточки будут переложены в коробку j, а коробка i использована не будет, т.е. количество коробок можно уменьшить.

Теперь покажем, что при 2^{k - 1}n < 2^k потребуется не менее k коробок. При k = 1, 2 это тривиально. Пусть это верно для некоторого k2, и пусть 2^kn < 2^{k + 1}. Предположим, что можно обойтись k коробками. Разобьем исходную стопку карточек на верхнюю и нижнюю части, содержащие не менее чем по 2^{k - 1} карточек. В силу доказанного выше, в некоторый момент потребуется занять «нижними» карточками k коробок уже для того, чтобы освободить исходную. «Верхние» карточки не могут при этом находиться в исходной коробке (до этого шага она еще не пуста, а верхняя из «нижних» карточек уже снята). Значит, они находятся в некоторой другой коробке i на самой верхней из «нижних» карточек (обозначим ее a). Так как «нижние» карточки занимают k > 1 коробок, то карточка a еще должна быть переложена, чтобы все они оказались в одной коробке. Для этого потребуется в некоторый момент занять «верхними» карточками k других коробок. В них не могут находиться «нижние» карточки (так как непосредственно под «верхней» карточкой может находиться лишь карточка a, а она еще находится в коробке i). Значит, все «нижние» карточки уже находятся в одной коробке --противоречие. Таким образом, потребуется не менее k + 1 коробок.

Ответ

11 коробок.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	62
Год	2006
вариант
Класс	10
задача
Номер	4