|
|
 |
Условие
Дана клетчатая полоска из 2n клеток, пронумерованных слева направо следующим образом:
1, 2, 3, ..., n, –n, ..., –2, –1
По этой полоске перемещают фишку, каждым ходом сдвигая её на то число клеток, которое указано в текущей клетке (вправо, если число положительно, и влево, если отрицательно). Известно, что фишка, начав с любой клетки, обойдёт все клетки полоски. Докажите, что число 2n + 1 простое.
Решение
Допустим, что оно не простое. Тогда среди чисел 2, 3, ..., n найдётся делитель d числа 2n + 1. Покажем, что начав с него, мы всегда будем попадать только на числа, кратные d (и тем самым всех чисел не обойдём). Для этого занумеруем числа слева направо. Заметим, что отрицательные числа в правой половине ровно на 2n + 1 меньше своего номера, поэтому, если номер кратен d, то и число тоже кратно d. При сдвиге вправо номер удваивается, поэтому делимость на d как его, так и числа в строке сохраняется. Ввиду симметрии делимость сохраняется и при сдвиге влево.
Замечания
4 балла
