МОШ 2021, 10 класс, задача 3
Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:
— перемещать камень из мешка в первую клетку полоски или обратно;
— если в клетке с номером лежит камень, то можно переложить камень из мешка в клетку с номером или обратно.
Можно ли, действуя по этим правилам, положить камень в клетку с номером ?
(А. Шень)
Ответ: да.
Решение. Заметим, для каждого действия есть обратное ему. Поэтому, если мы из ситуации , действуя по правилам, получили ситуацию , то из ситуации можем получить ситуацию , действуя по правилам. Покажем по индукции, что если есть запас в камней, то, действуя по вышеуказанным правилам, можно положить камень в любую клетку от до .
База индукции: . Очевидно.
Переход индукции. Допустим, мы доказали, что при помощи запаса в камней можно положить камень во все клетки до -ой. Пусть теперь есть чёрных камней и один красный камень. Будем действовать следующим образом:
Не вынимая красный камень из мешка, положим чёрный камень в -ю клетку. Это можно сделать по предположению индукции.
Положим красный камень в -ю клетку.
Проведём операции как в пункте , но противоположные и в обратном порядке. Понятно, что красный камень не помешает это сделать. В конце окажется, что все чёрные камни снова лежат в мешке, а на полоске ровно один камень — красный камень в клетке . Договоримся, что далее мы красный камень убирать не будем.
Клетки с номерами от до образуют полоску длины . К ней применимо предположение индукции для камней, так как красный камень позволяет совершать операции с самой левой клеткой этой полоски. Поэтому можно положить камень в последнюю клетку.
Таким образом, имея запас в камней, можно положить камень во все клетки с номерами от до .
Комментарий: На самом деле достаточно полоски длиной . Действительно, заметим, что среди клеток с номерами от по самый первый камень будет положен в клетку с номером . То есть, чтобы положить камень в -ю клетку, клетки с номерами от до использовать не обязательно, а значит, при запасе в камней можно положить камень в последнюю клетку полоски длины .