На доске написано N различных натуральных чисел, каждое из которых не превосходит 159. Для любых двух написанных на доске чисел a и b, таких, что a < b, ни одно из написанных чисел не делится на
а) Могли ли на доске быть написаны какие-то два числа из чисел 28, 29 и 30?
б) Среди написанных на доске чисел есть 13. Может ли N быть равно 20?
в) Найдите наибольшее значение N.
а) Поскольку 30 делится на и
а 29 делится на
это невозможно.
б) Рассмотрим остатки от деления данных чисел на 13. Всего разных остатков 13, поэтому среди 20 чисел найдутся два числа с одинаковыми остатками. Их разность будет кратна 13.
в) Рассмотрим числа 55, значит, все разности имеют вид
при
Поскольку все числа нечетны, 2n может делиться на них, только если n делится. Но n меньше любого из них. В этом примере 53 числа.
Допустим есть пример с 54 числами (если их больше — выкинем любые из них, оставив только 54). Рассуждения пункта б) показывают, что чисел меньших 54 там быть не может, а рассуждения пункта а) — что среди чисел не может быть соседних. Значит, из каждой пары (54, 55),
Ответ: а) нет, не могло; б) нет, не может; в) 53.

