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

Проект МЦНМО
при участии
школы 57
Задача 116592
Темы:    [ Четность и нечетность ]
[ НОД и НОК. Взаимная простота ]
[ Разложение на множители ]
[ Принцип Дирихле (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Петя выбрал натуральное число  a > 1  и выписал на доску пятнадцать чисел  1 + a,  1 + a²,  1 + a³,  ...,  1 + a15.  Затем он стёр несколько чисел так, что каждые два оставшихся числа взаимно просты. Какое наибольшее количество чисел могло остаться на доске?


Решение

  Заметим, что если k нечётно, то число  1 + ank  делится на  1 + an.  Каждое из чисел 1, 2, ..., 15 имеет один из видов k, 2k, 4k, 8k, где k нечётно. Таким образом, каждое из выписанных чисел делится либо на  1 + a,  либо на  1 + a²,  либо на  1 + a4,  либо на  1 + a8.  Поэтому, если мы возьмём хотя бы пять чисел, то среди них найдутся два, кратных одному и тому же числу, большему 1; значит, они не будут взаимно просты. Итак, оставшихся чисел не более четырёх.
  Четыре числа могли остаться: если  a = 2,  то можно оставить числа  1 + 2 = 3,  1 + 2² = 5,  1 + 24 = 17  и  1 + 28 = 257.  Все они попарно взаимно просты.


Ответ

4 числа.

Замечания

Можно показать, что при любом чётном a числа  1 + a,  1 + a²,  1 + a4,  1 + a8  попарно взаимно просты.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 4
Класс
Класс 10
Задача
Номер 10.6

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

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