Делимость разностей на доске

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Два выбранных числа
  2. Ответ: нет

    Сначала: Два выбранных числа

  3. Различные остатки по наименьшему числу

    Сначала: Ответ: нет

  4. Ответ: нет

    Сначала: Различные остатки по наименьшему числу

  5. Различные остатки по наименьшему числу

    Сначала: Ответ: нет

  6. Нечётный и смешанный случаи

    Сначала: Различные остатки по наименьшему числу

  7. Достижение нечётной границы

    Сначала: Нечётный и смешанный случаи

  8. Ответ

    Сначала: Достижение нечётной границы

Разобранный пример

На доске написано NN различных натуральных чисел, каждое из которых не превосходит 99. Для любых двух написанных на доске чисел aa и bb, таких, что a<ba<b, ни одно из написанных чисел не делится на b−ab-a, и ни одно из написанных чисел не является делителем числа b−ab-a.

а) Могли ли на доске быть написаны какие-то два числа из чисел 18, 19 и 20?

б) Среди написанных на доске чисел есть 17. Может ли NN быть равно 25?

в) Найдите наибольшее значение NN.

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Проверяем каждую возможную пару из трёх указанных чисел. Вычисляем её разность и проверяем, делится ли на неё одно из выбранных чисел или делит ли выбранное число эту разность. Если все пары нарушают условие, их присутствие невозможно.
T=((18;19;1;0);(18;20;2;0);(19;20;1;0))\mathcal T=\left(\left(18;19;1;0\right);\left(18;20;2;0\right);\left(19;20;1;0\right)\right)
Шаг 2. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Пусть pp - наименьшее написанное число. Никакие два написанных числа не имеют одинаковый остаток по модулю pp, иначе pp делило бы их разность. Поэтому N≤pN\leq p. В частности, присутствие заданного числа cc влечёт N≤p≤cN\leq p\leq c.
c=17c=17
N⩽17N\leqslant 17
N=25N=25
Шаг 2. Нет. Доказанное необходимое ограничение нарушено.
Шаг 1. Пусть pp - наименьшее написанное число. Никакие два написанных числа не имеют одинаковый остаток по модулю pp, иначе pp делило бы их разность. Поэтому N≤pN\leq p. В частности, присутствие заданного числа cc влечёт N≤p≤cN\leq p\leq c.
Шаг 2. Если есть хотя бы одно чётное число, разность 2 запрещена, поскольку она делит это чётное число; разность 1 запрещена всегда. Тогда соседние написанные числа различаются хотя бы на 3, и M≥p+3(N−1)≥4N−3M\geq p+3(N-1)\geq 4N-3. Если все числа нечётные, их промежутки не меньше 2, так что M≥p+2(N−1)M\geq p+2(N-1), где pp - нечётное число не меньше NN. Проверяем эти две доказанные границы.
M=99M=99
T=((33;97);(34;101);(35;103))\mathcal T=\left(\left(33;97\right);\left(34;101\right);\left(35;103\right)\right)
N⩽25N\leqslant 25
Шаг 3. Берём NN последовательных нечётных чисел, начиная с наименьшего нечётного p≥Np\geq N. Их разности - положительные чётные числа меньше 2p2p, поэтому они не могут быть кратны ни одному выбранному нечётному числу; и сами чётные разности не делят нечётные числа. Значит, конструкция удовлетворяет обоим запретам.
X1=(33;35;37;39;41;43;45;47;49;51;53;55;57;59;61;63;65;67;69;71;73;75;77;79;81;83;85;87;89;91;93;95;97)X_1=\left(33;35;37;39;41;43;45;47;49;51;53;55;57;59;61;63;65;67;69;71;73;75;77;79;81;83;85;87;89;91;93;95;97\right)
Шаг 4. Записываем вычисленную достижимую границу.
3333

Открыть задачу целиком

Попробовать самостоятельно