Аддитивная комбинаторика

Переформулируем задачу. Будем считать, что у нас номиналы копеек это соответственные остатки по модулю и нам нужно выбрать остатков сумма которых делится на Заметим, что монет не хватит так, как нам могут выпасть монет с остатком и монет с остатком Докажем, что для любого натурального нам достаточно вытащить монету, чтоб можно было выбрать монет с суммой, которая делится на Индукцией по количеству простых множителей числа

База индукции. Пусть — простое число. Пронумеруем элементы последовательности в порядке возрастания: Если при каком-нибудь то (в и мы нашли то, что требуется. В противном случае пусть при Последовательно применяя теорему Коши — Дэвенпорта, заключаем, что Следовательно, каждый элемент в том числе представим в виде суммы из слагаемых.

Докажем индукционный переход. Пусть где — простое, и пусть — данная последовательность. По утверждению задачи для простых (база индукции), мы можем последовательно выбирать наборы из чисел, сумма которых делится на Так мы сумеем выбрать различных наборов Действительно, если набора уже выбрано, то количество оставшихся элементов не меньше Для каждого положим По предположению индукции эта последовательность содержит подпоследовательность с суммой из элементов. Это дает нам требуемое подмножество из элементов с суммой, делящейся на