«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М2830

Условие задачи (2025, № 2) Задача М2830 // Квант. — 2025. — № 2. — Стр. 29; 2025. — № 5/6. — Стр. 22.

В ходу монеты номиналом в $a$‍‍ и $b$‍‍ дублонов, где $a$‍‍ и $b$‍‍ — данные взаимно простые натуральные числа, причём $a\lt b\lt100$‍.‍ Целое неотрицательное число $n$‍‍ называется удачным, если сумму в $n$‍‍ дублонов можно набрать, используя не более 1000 монет. Найдите количество удачных чисел.

Фольклор


Решение задачи (2025, № 5/6) Задача М2830 // Квант. — 2025. — № 2. — Стр. 29; 2025. — № 5/6. — Стр. 22.

Ответ: $1001b-\dfrac{b(b-1)}2$‍.

Если в наборе использовались хотя бы $b$‍‍ монет по $a$‍‍ дублонов, мы можем заменить их на $a$‍‍ монет по $b$‍‍ дублонов. При этом сумма номиналов не изменится, а общее количество монет уменьшится. Таким образом, из любого набора такими заменами можем получить набор с той же суммой, в котором не более $(b-1)$‍‍ монет по $a$‍‍ дублонов. Итак, далее рассматриваем только наборы, в которых от $0$‍‍ до $b-1$‍‍ монет по $a$‍‍ дублонов.

Заметим, что варианты с разным количеством монет по $a$‍‍ дублонов дают заведомо разные суммы, так как у них разные остатки при делении на $b$‍.‍ (Действительно, если $0\le i\lt j\le b-1$‍‍ — количества монет по $a$‍‍ дублонов, то соответствующие суммы при делении на $b$‍‍ дают такие же остатки, как $ia$‍‍ и $ja$‍.‍ Но $ja-ia=(j-i)a$‍‍ не делится на $b$‍,‍ поскольку $a$‍‍ и $b$‍‍ взаимно просты, а $0\lt j-i\lt b$‍.)

Зафиксируем количество $k$‍‍ монет по $a$‍‍ дублонов. Тогда к ним можно добавить 0, 1, $\ldots$‍,$1000-k$‍‍ монет по $b$‍‍ дублонов, и, очевидно, все получаемые при этом суммы будут различны. Видим, что для данного $k$‍‍ у нас есть $(1001-k)$‍‍ вариантов.

Суммируя по $k=0$‍,‍ 1, $\ldots$‍,$b-1$‍,‍ получаем итоговое количество вариантов: $$\begin{gather*} 1001+(1001-1)+(1001-2)+\ldots+\big(1001-(b-1)\big)=\\ =1001b-\big(1+2+\ldots+(b-1)\big)=1001b-\dfrac{b(b-1)}2. \end{gather*}$$


Метаданные Задача М2830 // Квант. — 2025. — № 2. — Стр. 29; 2025. — № 5/6. — Стр. 22.

Предмет
Математика
Номера

2025. — № 2. — Стр.  [условие]

2025. — № 5/6. — Стр.  [решение]

Описание
Задача М2830 // Квант. — 2025. — № 2. — Стр. 29; 2025. — № 5/6. — Стр. 22.
Ссылка
https://www.kvant.digital/problems/m2830/