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

Для доказательства этого утверждения используется принцип Дирихле (также известный как «принцип голубей и ящиков»). В математической формулировке он гласит: если $k+1$ предметов разместить в $k$ ящиках, то по крайней мере в одном ящике окажется более одного предмета. Ниже приведено пошаговое доказательство. 1. Определение остатков При делении любого целого числа на натуральное число $n$ возможны только $n$ различных вариантов остатков. Эти остатки образуют множество: $\{0,1,2,\dots ,n-1\}$2. Применение принципа Дирихле У нас имеется $n+1$ целое число. Рассмотрим остаток каждого из этих чисел при делении на $n$:

• Предметы: $n+1$ выбранное число. Ящики: $n$ возможных остатков от деления на $n$.

Согласно принципу Дирихле, так как количество чисел ( $n+1$) превышает количество возможных остатков ( $n$), найдутся как минимум два числа, которые имеют одинаковый остаток при делении на $n$. 3. Анализ разности Пусть эти два числа — $a$ и $b$. Раз они имеют одинаковый остаток $r$ при делении на $n$, их можно представить в виде:

• $a=n\cdot q_1+r$ $b=n\cdot q_2+r$

Где $q_1$ и $q_2$ — целые частные, а $r$ — общий остаток ( $0\le r<n$). Теперь найдем разность этих чисел: $a-b=(n\cdot q_1+r)-(n\cdot q_2+r)$ $a-b=n\cdot q_1-n\cdot q_2$ $a-b=n\cdot (q_1-q_2)$4. Вывод Так как разность $(a-b)$ представлена в виде произведения числа $n$ и целого числа $(q_1-q_2)$, это по определению означает, что разность $a-b$ делится на $n$ без остатка.

Что и требовалось доказать.

Я могу разобрать для вас аналогичную задачу, например, доказать, что среди любых $n$ чисел найдется несколько, сумма которых делится на $n$. Хотите рассмотреть это доказательство?