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

Докажем индукцией по что среди сумм всевозможных подпоследовательностей есть хотя бы различных остатков по модулю Для это очевидно, так как даёт один остаток.

Пусть утверждение верно для чисел (), добавим к ним Пусть до этого среди сумм подпоследовательностей встречались различные остатки Рассмотрим остатки

Ясно, что они различные. Предположим, что это просто перестановка остатков Тогда получаем, что

Получается, что кратно Однако а значит, что противоречит условию. Следовательно, среди чисел

есть новый остаток. Переход доказан.

Тогда среди сумм всевозможных подпоследовательностей чисел есть любой остаток по модулю что и требовалось.