|
|
 |
Условие
Имеются одна красная и k (k > 1) синих ячеек, а также колода из 2n карт, занумерованных числами от 1 до 2n. Первоначально вся колода лежит в произвольном порядке в красной ячейке. Из любой ячейки можно взять верхнюю карту и переложить её либо в пустую ячейку, либо поверх карты с номером, большим на единицу. При каком наибольшем n можно такими операциями переложить всю колоду в одну из синих ячеек?
Решение
Построим пример, показывающий, что при n ≥ k это невозможно. Пусть карты (сверху вниз) первоначально лежат так: сначала все нечётные (в произвольном порядке), потом чётные, причём верхняя из них – карта 2n. Тогда первые k ходов однозначно определены – нечётные карты перекладываются на свободные позиции; следующий ход, если n > k, невозможен, а если n = k, то можно лишь переложить карту 2n – 1 обратно в изначальную стопку, что бессмысленно, ибо мы вернулись к предыдущей позиции. Поэтому эту стопку переложить нельзя.
Пусть n < k. Покажем, как можно организовать процесс перекладывания.
Разобьём все карты на пары (1, 2), (2n – 1, 2n) и сопоставим каждой паре по незанятой ячейке (хотя бы одна ячейка не сопоставлена никакой паре; назовём её свободной).
Теперь каждую карту сверху красной ячейки попытаемся положить в её ячейку. Это может не получиться, только если эта карта имеет номер 2i, а карта 2i – 1 уже лежит в ячейке; но тогда можно переместить карту 2i в свободную ячейку, сверху положить карту 2i – 1, сопоставить этой ячейке нашу пару, а прежнюю сопоставленную назвать свободной. Таким образом, в результате мы получим карты, разложенные в ячейки по парам. Теперь, используя свободную ячейку, легко собрать их в колоду в правильном порядке.
Ответ
При n = k – 1.
