Назад
Задача

Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:

– перемещать камень из мешка в первую клетку полоски или обратно;

– если в клетке с номером $i$ лежит камень, то можно переложить камень из мешка в клетку с номером $i + 1$ или обратно.

Можно ли, действуя по этим правилам, положить камень в клетку с номером 1000?

Решение

Заметим, для каждого действия есть обратное ему. Поэтому если мы из ситуации $A$, действуя по правилам, получили ситуацию $B$, то из ситуации $B$ можем получить ситуацию $A$, действуя по правилам.

Покажем по индукции, что если есть запас в $n$ камней, то, действуя по вышеуказанным правилам, можно положить камень в любую клетку от $1$ до $2^{n}-1$.

База индукции: $n=1$. Очевидно.

Переход индукции. Допустим, мы доказали, что при помощи запаса в $n$ камней можно положить камень во все клетки до $(2^n-1)$-й. Пусть теперь есть $n$ черных камней и один красный камень. Будем действовать следующим образом:

  1. Не вынимая красный камень из мешка, добьемся того, чтобы в $(2^n-1)$-й клетке оказался черный камень. Это можно сделать по предположению индукции.

  2. Положим красный камень в $2^n$-ю клетку.

  3. Проведем операции как в пункте (1), но противоположные и в обратном порядке. Понятно, что красный камень не помешает это сделать. В конце окажется, что все черные камни снова лежат в мешке, а на полоске ровно один камень – красный камень в клетке $2^n$. Договоримся, что далее мы красный камень убирать не будем.

  4. Клетки с номерами от $2^n+1$ до $2^{n+1}-1$ образуют полоску длиной $2^{n}-1$. К ней применимо предположение индукции для $n$ камней, так как красный камень позволяет совершать операции с самой левой клеткой этой полоски. Поэтому можно положить камень в последнюю клетку.

Таким образом, имея запас в 10 камней, можно положить камень во все клетки с номерами от $1$ до $1023= 2^{10}-1$.

Ответ

Да.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет