Задача
Есть 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, получим искомую сумму.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь