Задача 4. Остатки Саши и Таи

Чья сумма может быть больше

Пусть число равно $N$. Остатки Саши (при делении на $302$, $303$, $304$) обозначим $a_1$, $a_2$, $a_3$, остатки Таи (при делении на $100$, $101$, $102$) — $b_1$, $b_2$, $b_3$. Суммы: $S = a_1 + a_2 + a_3$ у Саши и $T = b_1 + b_2 + b_3$ у Таи.

Остаток всегда меньше делителя. Поэтому

Значит, сумма Таи не может быть больше суммы Саши на $777$: даже если $S = 0$, разница не больше $300$. Остаётся один случай: $S - T = 777$.

А этот случай одной оценкой не исключить: сумма Саши бывает до $301 + 302 + 303 = 906$. Если попробовать разные числа, попадаются разности совсем рядом: при $N = 182\,700$ получается $886 - 110 = 776$. Нужна ещё одна идея.

Чётные делители

Четыре делителя из шести чётные: $302$, $304$, $100$, $102$. Если делитель $d$ чётный и $N = d\cdot q + r$, то $d\cdot q$ — чётное число. Поэтому $N$ и $r$ одинаковой чётности: чётное плюс $r$ чётно ровно тогда, когда чётно $r$.

Например, $2024 = 302\cdot 6 + 212$: и $2024$, и $212$ чётные.

Значит, $a_1$, $a_3$, $b_1$, $b_3$ — все той же чётности, что и $N$. Сумма двух чисел одной чётности чётна, поэтому $a_1 + a_3$ и $b_1 + b_3$ — чётные, и чётна их разность

Делители 303 и 101

Остались делители $303$ у Саши и $101$ у Таи, а $303 = 3\cdot 101$. Если $N = 303q + a_2$, то

Из $N$ вычли целое число раз по $101$ и получили $a_2$. Поэтому остаток $N$ при делении на $101$ — это остаток от деления на $101$ самого $a_2$, то есть $b_2$.

А $a_2 < 303 = 3\cdot 101$, так что $101$ помещается в $a_2$ ноль, один или два раза: $a_2 = 101j + b_2$, где $j = 0$, $1$ или $2$. Значит, разница $a_2 - b_2$ равна $0$, $101$ или $202$.

Например, при $N = 2024$: $a_2 = 206 = 2\cdot 101 + 4$ и $b_2 = 4$, разница $202$.

Сложим и сравним

Разность сумм складывается из двух частей:

Число $777$ нечётное, а $A$ чётное (шаг 2). Значит, нечётной должна быть добавка $a_2 - b_2$. Из $0$, $101$, $202$ нечётное только $101$.

Но тогда

потому что $a_1 \le 301$, $a_3 \le 303$, а остатки Таи не меньше $0$. А $705 < 777$ — противоречие.

Итак, ни при каком числе $N$ суммы Саши и Таи не отличаются на $777$. Ответ: нет, не могут.

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

Рассуждение то же, меняются только числа.

Чья сумма больше. Сумма Кати не больше $199 + 200 + 201 = 600 < 1445$, поэтому больше на $1445$ может быть только сумма Вани (она бывает до $601 + 602 + 603 = 1806$).

Чётные делители. $602$, $604$, $200$, $202$ чётные, поэтому остатки при делении на них той же чётности, что и число. Часть разности, которая приходится на эти четыре остатка, чётна.

Делители 603 и 201. $603 = 3\cdot 201$, поэтому остаток Кати при делении на $201$ — это остаток от деления на $201$ остатка Вани при делении на $603$. Этот остаток Вани меньше $603$, так что он больше Катиного на $0$, на $201$ или на $402$.

Итог. $1445$ нечётное, значит, нужна добавка $201$, и тогда разность не больше $601 + 603 + 201 = 1405 < 1445$. Ответ: нет, не могут.

Как и в первом варианте, рядом с целью бывают чётные разности: например, $N = 3\,672\,800$ даёт разность $1446$.