На доске написано N различных натуральных чисел, каждое из которых не превосходит 99. Для любых двух написанных на доске чисел a и b, таких, что a<b, ни одно из написанных чисел не делится на b−a, и ни одно из написанных чисел не является делителем числа b−a.
а) Могли ли на доске быть написаны какие-то два числа из чисел 18, 19 и 20?
б) Среди написанных на доске чисел есть 17. Может ли N быть равно 25?
в) Найдите наибольшее значение N.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Проверяем каждую возможную пару из трёх указанных чисел. Вычисляем её разность и проверяем, делится ли на неё одно из выбранных чисел или делит ли выбранное число эту разность. Если все пары нарушают условие, их присутствие невозможно.
T=((18;19;1;0);(18;20;2;0);(19;20;1;0))
Шаг 2. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Пусть p - наименьшее написанное число. Никакие два написанных числа не имеют одинаковый остаток по модулю p, иначе p делило бы их разность. Поэтому N≤p. В частности, присутствие заданного числа c влечёт N≤p≤c.
c=17
N⩽17
N=25
Шаг 2. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Пусть p - наименьшее написанное число. Никакие два написанных числа не имеют одинаковый остаток по модулю p, иначе p делило бы их разность. Поэтому N≤p. В частности, присутствие заданного числа c влечёт N≤p≤c.
Шаг 2. Если есть хотя бы одно чётное число, разность 2 запрещена, поскольку она делит это чётное число; разность 1 запрещена всегда. Тогда соседние написанные числа различаются хотя бы на 3, и M≥p+3(N−1)≥4N−3. Если все числа нечётные, их промежутки не меньше 2, так что M≥p+2(N−1), где p - нечётное число не меньше N. Проверяем эти две доказанные границы.
M=99
T=((33;97);(34;101);(35;103))
N⩽25
Шаг 3. Берём N последовательных нечётных чисел, начиная с наименьшего нечётного p≥N. Их разности - положительные чётные числа меньше 2p, поэтому они не могут быть кратны ни одному выбранному нечётному числу; и сами чётные разности не делят нечётные числа. Значит, конструкция удовлетворяет обоим запретам.