Задача 4. Крупноостаточные числа

Какие бывают суммы остатков

Остаток при делении на $125$ — это число от $0$ до $124$, а при делении на $80$ — от $0$ до $79$. Значит, сумма двух остатков бывает от $0$ до $124 + 79 = 203$.

Например, $777 = 125\cdot 6 + 27$ и $777 = 80\cdot 9 + 57$. Сумма остатков $27 + 57 = 84$ меньше $102$, поэтому $777$ — не крупноостаточное. А у числа $1999$ остатки самые большие, $124$ и $79$: ведь $2000$ делится и на $125$, и на $80$.

Главное наблюдение: $101 + 102 = 203$. Порог $102$ стоит ровно посередине: «маленьких» сумм от $0$ до $101$ столько же, сколько «больших» от $102$ до $203$, — по $102$. Если у двух чисел суммы остатков вместе дают $203$, то крупноостаточное из них ровно одно. Поэтому попробуем разбить все числа на такие пары.

Ищем напарника

Нам нужен напарник, у которого остатки «дополняют» остатки числа $n$: если у $n$ остатки $a$ и $b$, то у напарника — $124 - a$ и $79 - b$. Тогда суммы остатков пары вместе дадут $124 + 79 = 203$.

Как такого напарника найти? У числа с остатками $0$ и $0$ напарник должен иметь самые большие остатки $124$ и $79$. Таково число $999\,999$: оно на единицу меньше $1\,000\,000$, а

Когда $n$ увеличивается на $1$, его остатки (пока не начнётся новая коробка) тоже растут на $1$, а остатки напарника должны уменьшаться. Поэтому напарником числа $n$ возьмём

Осталось доказать, что остатки у $m$ всегда «дополняющие», а не только у первых чисел.

Почему остатки дополняют друг друга

Представим, что $n$ конфет разложили по коробкам по $125$ штук: получилось $k$ полных коробок, а в неполной $a$ конфет, то есть $n = 125k + a$. Так же разложим $m$ конфет: $m = 125k' + a'$. Остатки $a$ и $a'$ — от $0$ до $124$.

Сложим все конфеты и добавим ещё одну. Получится $n + m + 1 = 1\,000\,000$ конфет — ровно $8000$ полных коробок:

Полные коробки $k + k'$ так и остаются полными, значит, конфеты двух неполных коробок вместе с добавленной тоже заполняют целое число коробок: $a + a' + 1$ делится на $125$. Но $a + a' + 1$ — от $1$ до $124 + 124 + 1 = 249$: это больше нуля и меньше двух коробок. Значит, ровно одна коробка:

Точно так же с коробками по $80$: $1\,000\,000 = 80\cdot 12\,500$, и $b + b' + 1 = 80$, то есть $b' = 79 - b$.

В каждой паре ровно одно крупноостаточное

Пусть сумма остатков числа $n$ равна $s = a + b$. Тогда у напарника

• Если $n$ крупноостаточное, то $s \ge 102$, и $s' = 203 - s \le 101$: напарник не крупноостаточный.

• Если $n$ не крупноостаточное, то $s \le 101$, и $s' = 203 - s \ge 102$: напарник крупноостаточный.

Пример: напарник числа $777$ — число $999\,222$. Его остатки $97 = 124 - 27$ и $22 = 79 - 57$, сумма $119$, и $84 + 119 = 203$. Крупноостаточное в этой паре — $999\,222$.

Считаем

Разобьём числа от $1$ до $999\,998$ на пары «$n$ и $999\,999 - n$»:

Каждое число попадает ровно в одну пару. В паре само с собой число быть не может: равенство $n = 999\,999 - n$ означало бы $2n = 999\,999$, а $999\,999$ нечётно. Пар $499\,999$, в каждой ровно одно крупноостаточное — всего их здесь $499\,999$.

Без пары остались два числа. У $999\,999$ остатки $124$ и $79$, сумма $203$ — оно крупноостаточное. У $1\,000\,000$ остатки $0$ и $0$ — нет.

Итого крупноостаточных чисел $499\,999 + 1 = 500\,000$ — ровно половина.

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

Решение то же, меняются только числа. Остаток при делении на $160$ — от $0$ до $159$, на $75$ — от $0$ до $74$, сумма остатков — от $0$ до $159 + 74 = 233$. И снова порог посередине: $116 + 117 = 233$.

Число $3\,000\,000$ делится на оба делителя:

поэтому напарником числа $n$ берём $2\,999\,999 - n$. Как в шаге 3, $n + (2\,999\,999 - n) + 1 = 3\,000\,000$ — целое число коробок и по $160$, и по $75$. Поэтому остатки пары $a$ и $a'$ при делении на $160$ дают число $a + a' + 1$, которое делится на $160$; оно от $1$ до $159 + 159 + 1 = 319$, то есть меньше двух коробок, значит, $a + a' + 1 = 160$ и $a + a' = 159$. Так же остатки $b$ и $b'$ при делении на $75$: $b + b' + 1$ от $1$ до $149$ и делится на $75$, значит, $b + b' = 74$.

Суммы остатков пары вместе равны $159 + 74 = 233$, и в паре ровно одно крупноостаточное: если у одного сумма не меньше $117$, у другого не больше $233 - 117 = 116$; и наоборот, если у одного не больше $116$, у другого не меньше $233 - 116 = 117$.

Число $2\,999\,999$ нечётно, поэтому $n \ne 2\,999\,999 - n$ — число само себе не пара. Числа от $1$ до $2\,999\,998$ разбиваются на $1\,499\,999$ пар $(n;\ 2\,999\,999 - n)$, $n = 1, \dots, 1\,499\,999$, — столько крупноостаточных в них. Остаются $2\,999\,999$ (остатки $159$ и $74$, сумма $233$ — крупноостаточное) и $3\,000\,000$ (остатки $0$ и $0$ — нет). Итого $1\,499\,999 + 1 = 1\,500\,000$. Прямой перебор всех чисел до $3\,000\,000$ дал то же число.