|
|
 |
Условие
Есть 100 купюр двух типов: по a и b рублей, причём a ≠ b (mod 101).
Доказать, что можно выбрать несколько купюр так, что полученная сумма (в рублях) делится на 101.
Решение
Пусть имеется m ≤ 50 купюр по a рублей и n = 100 – m купюр по b рублей. Рассмотрим суммы a, a + b, 2a + b, 2a + 2b, 2a + 3b, 3a + 3b, ..., ma + mb, ma + (m + 1)b, ..., ma + nb. Всего их 2m + (n – m) = 100. Есть три возможности.
1) Среди этих сумм найдётся кратная 101. Это и будет искомая сумма.
2) Найдутся две суммы, сравнимые по модулю 101. Тогда искомая сумма – их разность.
3) Остатки от деления этих сумм на 101 принимают все значения от 1 до 100. Тогда какая-то из них (но не a) сравнима с b по модулю 101. Вычитая из неё b, получим искомую сумму.
Замечания
В книге Иванова требовалось только, чтобы числа a и b были не равны. Но тогда утверждение неверно: например, из 100 купюр достоинством 1 и 102 рубля нельзя набрать сумму, кратную 101.
Источники и прецеденты использования
| книга | |
| Автор | Иванов С.В. |
| Название | Математический кружок |
| глава | |
| Номер | 12 |
| Название | Уравнения в целых числах |
| Тема | Уравнения в целых числах |
| задача | |
| Номер | 23 |
