Дано: n + 1 натуральных чисел.
Найти: Доказать, что среди этих чисел можно выбрать два таких, что их разность делится на n.
Решение:
1. Рассмотрим n + 1 натуральных чисел: a1, a2, ..., a(n+1).
2. Определим каждое из этих чисел по модулю n. То есть для каждого числа ai найдём остаток при делении на n. Остатки могут принимать значения от 0 до n-1, всего n возможных остатков.
3. По принципу Дирихле, если у нас есть n + 1 чисел и только n возможных остатков при делении на n, то среди этих чисел найдутся как минимум два числа, имеющие одинаковый остаток при делении на n. Пусть это числа ai и aj.
4. Если числа ai и aj имеют одинаковый остаток при делении на n, то:
ai ≡ r (mod n) и aj ≡ r (mod n),
где r — общий остаток.
5. Рассмотрим разность этих двух чисел:
ai - aj.
Поскольку оба числа имеют одинаковый остаток при делении на n, разность будет:
ai - aj ≡ r - r (mod n),
ai - aj ≡ 0 (mod n).
6. Таким образом, разность двух чисел с одинаковым остатком при делении на n делится на n.
Ответ: Среди любых n + 1 натуральных чисел найдутся два числа, разность которых делится на n.