|
|
 |
Условие
Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:
– перемещать камень из мешка в первую клетку полоски или обратно;
– если в клетке с номером $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$.
Ответ
Да.Замечания
На самом деле достаточно полоски длиной 1000. Действительно, заметим, что среди клеток с номерами от 1000 до 1023 самый первый камень будет положен в клетку с номером 1000.То есть, чтобы положить камень в 1000-ю клетку, клетки с номерами от 1001 до 1023 использовать не обязательно, а значит, при запасе в 10 камней можно положить камень в последнюю клетку полоски длиной 1000.
