Задача 3. Ровно на одно слагаемое

Предположим, что Федя прав

Пусть число $N$ делится ровно на одно слагаемое в каждой паре $a + b = 4000$ с различными $a$ и $b$. Покажем, что тогда в какой-то паре получится невозможное. Нам хватит трёх пар.

Понадобятся два свойства делимости.

• Если $N$ делится на число, то делится и на любой его делитель. Например, если $N$ делится на $3000$, то делится и на $1000$.

• Если $N$ делится на два взаимно простых числа (у них нет общих делителей, кроме $1$), то делится и на их произведение. Например, если $N$ делится на $3$ и на $1000$, то делится и на $3000$: в разложение $N$ на простые множители входят и тройка, и все множители числа $1000 = 2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 5$, а общих множителей у $3$ и $1000$ нет.

Второе свойство без взаимной простоты неверно: $12$ делится на $4$ и на $6$, но не делится на $24$.

Пара 1000 + 3000: выбор вынужден

В этой паре одно слагаемое — делитель другого: $3000 = 3\cdot 1000$. Если бы $N$ делилось на $3000$, то делилось бы и на $1000$ — на оба слагаемых сразу, а Федя говорит «ровно на одно».

Значит, остаётся единственная возможность: $N$ делится на $1000$ и не делится на $3000$.

N не делится на 3, и пара 1999 + 2001

Если бы $N$ делилось на $3$, то, делясь ещё и на $1000$, оно делилось бы на $3\cdot 1000 = 3000$ — ведь $3$ и $1000$ взаимно просты. Но на $3000$ число $N$ не делится. Значит, $N$ не делится на $3$, а потому не делится ни на одно число, кратное $3$.

Число $2001$ кратно $3$ (сумма цифр равна $3$): $2001 = 3\cdot 667$. Значит, на $2001$ число $N$ не делится. А в паре $1999 + 2001$ оно должно делиться ровно на одно слагаемое — следовательно, $N$ делится на $1999$.

Пара 2 + 3998: противоречие

Число $N$ делится на $1000$, значит, оно чётное — делится на $2$. Ещё $N$ делится на $1999$, а $1999$ нечётное, поэтому $2$ и $1999$ взаимно просты. Значит, $N$ делится на их произведение

Но $2 + 3998 = 4000$, и в этой паре $N$ делится на оба слагаемых, а по словам Феди — ровно на одно. Противоречие.

Значит, предположение было неверным: какое бы натуральное $N$ ни изучал Федя, найдётся разбиение числа $4000$, для которого его утверждение ложно.

Как найти такую цепочку

Почему начали с $1000 + 3000$? Если $a$ — делитель $4000$ и $a < 2000$, то в паре $a + (4000 - a)$ большее слагаемое делится на $a$. В такой паре у Феди остаётся единственный выбор — меньшее слагаемое, и сразу появляется число, на которое $N$ не делится. Дальше работают два хода:

• если $N$ не делится на $x$, то не делится и на кратные $x$, а в их парах делит второе слагаемое;

• известные делители $N$ можно перемножать, если они взаимно просты.

Одной заранее выбранной пары не хватит: в паре $a + b$ при $a < b$ Федя прав, например, для $N = a$. Ошибка у каждого $N$ своя: для $N = 1$ — уже в паре $1000 + 3000$, для $N = 1000$ — в паре $1999 + 2001$, для $N = 1\,999\,000$ — в паре $2 + 3998$. Поэтому доказательство и устроено цепочкой: каждая пара даёт факт для следующей.

Цепочек много. Модель, например, находит такую: $N$ не делится на $3$, значит, в паре $3 + 3997$ делит $3997 = 7\cdot 571$; тогда $N$ делится на взаимно простые $7$ и $500$, то есть на $3500$, — а в паре $500 + 3500$ уже делит $500$. Годится любая цепочка, где каждый шаг следует из слов Феди.

Второй вариант

Утверждение Саши — то же самое: «делится на одно из них и не делится на другое» значит «ровно на одно». Меняется сумма — $2000$ вместо $4000$, поэтому берём другие пары.

• Пара $500 + 1500$: $1500 = 3\cdot 500$. Как в шаге 2, $M$ делится на $500$ и не делится на $1500$.

• $M$ не делится на $3$: иначе, делясь на взаимно простые $3$ и $500$, оно делилось бы на $1500$.

• Пара $998 + 1002$: $1002 = 3\cdot 334$ кратно $3$, поэтому $M$ на $1002$ не делится и, по словам Саши, делится на $998 = 2\cdot 499$. Значит, $M$ делится на $499$.

• Пара $4 + 1996$: $M$ делится на $500 = 4\cdot 125$, значит, и на $4$; ещё $M$ делится на $499$, а $499$ нечётное, так что $4$ и $499$ взаимно просты. Поэтому $M$ делится на $4\cdot 499 = 1996$ — на оба слагаемых пары $4 + 1996$. Противоречие: Саша ошибается.

Почему пары другие: прямой перенос не работает. Пара $999 + 1001$ дала бы делитель $1001$, но $2\cdot 1001 = 2002$ уже больше $2000$, и пары $2 + 2002$ нет. Поэтому берём $998 = 2\cdot 499$ и вместо $2$ — делитель $4$ числа $500$: $4 + 1996 = 2000$.