Докажите, что из любых n+1 целых чисел можно выбрать два числа, разность которых делится на n

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

Докажем это утверждение методом принципа Дирихле.

Пусть у нас есть n+1 целых чисел a1, a2, ..., a(n+1). Рассмотрим все остатки чисел при делении на n: 0, 1, 2, ..., n-1.

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

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