Среди любых n+1 натуральных чисел найдутся два числа, которые при делении на n дают одинаковые остатки?

Предыдущий
вопрос Следующий
вопрос

Да, такое утверждение верно.

Для доказательства этого факта можно воспользоваться теоремой о китайском остатке. Рассмотрим набор из n+1 числа: a_1, a_2, ..., a_n+1. Рассмотрим остатки этих чисел при делении на n, то есть рассмотрим числа a_1 mod n, a_2 mod n, ..., a_n+1 mod n.

Если все эти остатки различны, то есть каждый остаток от 0 до n-1 встречается среди этих чисел, то по принципу Дирихле найдутся два числа, остатки от деления которых на n совпадают.

Если же какие-то остатки совпадают, то это означает, что найдутся два числа из набора, которые имеют одинаковый остаток при делении на n.

Таким образом, среди любых n+1 натуральных чисел найдутся два числа, которые при делении на n дают одинаковые остатки.