ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116713
Темы:    [ Арифметическая прогрессия ]
[ Делимость чисел. Общие свойства ]
[ Доказательство от противного ]
Сложность: 3
Классы: 10,11
В корзину
Прислать комментарий

Условие

Дана клетчатая полоска из 2n клеток, пронумерованных слева направо следующим образом:

1, 2, 3, ..., n, –n, ..., –2, –1

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


Решение

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

Замечания

4 балла

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .