В школе, где учатся Поля, Маня и Дуня, есть длинный коридор вдоль одной из стен которого расположен длинный ряд из n ячеек, занумерованных натуральными числами от 1 до n, закрывающихся на замки, в которых школьники могут хранить свои личные вещи. Однажды, придя в школу в выходной день, Поля обнаружила все ячейки открытыми. Она стала обходить ряд ячеек сначала до конца, закрывая на замок каждую вторую ячейку. Достигнув конца ряда, она развернулась и снова стала закрывать на замок каждую вторую ячейку из тех, которые еще были открыты. Таким образом, Поля продолжала обходить ряд и закрывать на замок ячейки до тех пор, пока осталась незакрытой одна ячейка.
Обозначим номер последней открытой ячейки. Например, если количество ячеек
то
как показано на рисунке.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
| → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | ← | ||||||||
| → | 3 | 7 | 11 | 15 | ||||||||||||
| 3 | 11 | ← |
а) Найдите
Докажите, что:
б) не существует натурального числа n, такого что
в) существует бесконечное множество натуральных чисел n, таких, что
а) Во время первого прохода слева направо Поля закроет все ячейки с чётными номерами. Открытыми останутся ячейки с нечётными номерами: 1, 3, …, 47, 49.
Во время второго прохода справа налево Поля закроет ячейки, номера которых при делении на 4 дают в остатке 3: 47, 43, 39, …, 3. Открытыми останутся ячейки, номера которых при делении на 4 дают в остатке 1: 1, 5, …, 45, 49.
Во время третьего прохода слева направо Поля закроет все ячейки, номера которых дают при делении на 8 в остатке 5: 5, 13, 21, 29, 37, 45. Открытыми останутся ячейки, номера которых при делении на 8 дают в остатке 1: 1, 9, 17, 25, 33, 41, 49.
Во время четвёртого прохода справа налево Поля закроет ячейки, номера которых при делении на 16 дают в остатке 9: 41, 25, 9. Открытыми останутся ячейки, номера которых при делении на 16 дают в остатке 1: 1, 17, 33, 49.
Во время пятого прохода слева направо Поля закроет все ячейки, номера которых дают при делении на 32 в остатке 17: 17, 49. Открытыми останутся ячейки, номера которых при делении на 32 дают в остатке 1: 1, 33.
Во время шестого прохода справа налево Поля закроет ячейку 1, номер которой при делении на 64 даёт в остатке 1. Открытой останется ячейка 33, номер которой при делении на 64 даёт в остатке 33.
Таким образом,
б) Предположим, что нашлось n, такое, что т. е. последней открытой ячейкой является ячейка с номером 2013.
Прежде всего, заметим, что если n — чётно, то поскольку последняя ячейка с номером n будет закрыта при первом проходе ряда слева направо, таким образом, если бы эта ячейка отсутствовала, то на значении номера последней открытой ячейки это бы не отразилось. Значит, можно считать n нечётным. Во время первого прохода слева направо Поля закроет все ячейки с чётными номерами. Открытыми останутся ячейки с нечётными номерами, то есть с номерами m, дающими при делении
Число 2013 при делении
Поскольку ячейка с номером 1 осталась открытой, то во время третьего прохода слева направо Поля закроет ячейки, номера которых при делении
в) Пусть где
тогда
После первых шести проходов из первых 50 ячеек останется открытой одна ячейка с номером 33, а количество открытых ячеек с номерами, большими 50, уменьшится в
раз и будет равно
Если
то после каждой пары проходов слева направо и справа налево ячейка с номером 33 будет оставаться открытой, а количество ячеек с номерами, большими 50, будет уменьшаться
Ответ: а) 33; в) 33.

