Задача: В коробке лежат карточки, занумерованные натуральными числами от 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 это тривиально. Пусть это верно для некоторого k ≥ 2, и пусть 2^k ≤ n < 2^{k+1}. Предположим, что можно обойтись k коробками. Разобьём исходную стопку карточек на верхнюю и нижнюю части, содержащие не менее чем по 2^{k−1} карточек. В силу доказанного выше, в некоторый момент потребуется занять «нижними» карточками k коробок уже для того, чтобы освободить исходную. «Верхние» карточки не могут при этом находиться в исходной коробке (до этого шага она ещё не пуста, а верхняя из «нижних» карточек уже снята). Значит, они находятся в некоторой другой коробке i на самой верхней из «нижних» карточек (обозначим её a). Так как «нижние» карточки занимают k > 1 коробок, то карточка a ещё должна быть переложена, чтобы все они оказались в одной коробке. Для этого потребуется в некоторый момент занять «верхними» карточками k других коробок. В них не могут находиться «нижние» карточки (поскольку непосредственно под «верхней» карточкой может находиться лишь карточка a, а она ещё находится в коробке i). Значит, все «нижние» карточки уже находятся в одной коробке — противоречие. Таким образом, потребуется не менее k + 1 коробок.
Ответ: 11