Разделы 
Дополнительно
Задача по математике - 1972
2019-01-22 
Имеются одна красная и $k (k > 1)$ синих ячеек, а также колода из $2n$ карт, занумерованных числами от 1 до $2n$. Первоначально вся колода лежит в произвольном порядке в красной ячейке. Из любой ячейки можно взять верхнюю карту и переложить ее либо в пустую ячейку, либо поверх карты с номером, большим на единицу. При каком наибольшем $n$ можно такими операциями переложить всю колоду в одну из синих ячеек?
Решение:
Построим пример, показывающий, что при $n \geq k$ это невозможно. Пусть карты (сверху вниз) первоначально лежат так: сначала все нечетные (в произвольном порядке), потом четные, причем верхняя из них - карта $2n$. Тогда первые $k$ ходов однозначно определены - нечетные карты перекладываются на свободные позиции; следующий ход, если $n > к$, невозможен, а если $n = k$, то можно лишь переложить карту $2n - 1$ обратно в изначальную стопку, что бессмысленно, ибо мы вернулись к предыдущей позиции. Поэтому эту стопку переложить нельзя.
Пусть $n < k$. Покажем, как можно организовать процесс перекладывания. Разобьем все карты на пары $(1, 2), \cdots, (2n - 1, 2n)$ и сопоставим каждой паре по незанятой ячейке (хотя бы одна ячейка не сопоставлена никакой паре; назовем ее свободной). Теперь каждую карту сверху красной ячейки попытаемся положить в «ее» ячейку. Это может не получиться, только если эта карта имеет номер $2i$, а карта $2i - 1$ уже лежит в ячейке; но тогда можно переместить карту $2i$ в свободную ячейку, сверху положить карту $2i - 1$, сопоставить этой ячейке нашу пару, а прежнюю сопоставленную назвать свободной. Таким образом, в результате мы получим карты, разложенные в ячейки по парам. Теперь, используя свободную ячейку, легко собрать их в колоду в правильном порядке.
Ответ. $n = k - 1$.
Имеются одна красная и $k (k > 1)$ синих ячеек, а также колода из $2n$ карт, занумерованных числами от 1 до $2n$. Первоначально вся колода лежит в произвольном порядке в красной ячейке. Из любой ячейки можно взять верхнюю карту и переложить ее либо в пустую ячейку, либо поверх карты с номером, большим на единицу. При каком наибольшем $n$ можно такими операциями переложить всю колоду в одну из синих ячеек?
Решение:
Построим пример, показывающий, что при $n \geq k$ это невозможно. Пусть карты (сверху вниз) первоначально лежат так: сначала все нечетные (в произвольном порядке), потом четные, причем верхняя из них - карта $2n$. Тогда первые $k$ ходов однозначно определены - нечетные карты перекладываются на свободные позиции; следующий ход, если $n > к$, невозможен, а если $n = k$, то можно лишь переложить карту $2n - 1$ обратно в изначальную стопку, что бессмысленно, ибо мы вернулись к предыдущей позиции. Поэтому эту стопку переложить нельзя.
Пусть $n < k$. Покажем, как можно организовать процесс перекладывания. Разобьем все карты на пары $(1, 2), \cdots, (2n - 1, 2n)$ и сопоставим каждой паре по незанятой ячейке (хотя бы одна ячейка не сопоставлена никакой паре; назовем ее свободной). Теперь каждую карту сверху красной ячейки попытаемся положить в «ее» ячейку. Это может не получиться, только если эта карта имеет номер $2i$, а карта $2i - 1$ уже лежит в ячейке; но тогда можно переместить карту $2i$ в свободную ячейку, сверху положить карту $2i - 1$, сопоставить этой ячейке нашу пару, а прежнюю сопоставленную назвать свободной. Таким образом, в результате мы получим карты, разложенные в ячейки по парам. Теперь, используя свободную ячейку, легко собрать их в колоду в правильном порядке.
Ответ. $n = k - 1$.
