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

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

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

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