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

числу n.

Для доказательства данного утверждения воспользуемся методом математической индукции.

Шаг 1: Базовый случай (n = 1):
Рассмотрим 2 натуральных числа - 1 и 2. Разность между этими числами равна 2 - 1 = 1, что является кратным числу 1.

Шаг 2: Предположение индукции:
Предположим, что среди n+1 натуральных чисел найдутся два числа, разность которых является кратной числу n.

Шаг 3: Индукционный переход:
Докажем, что среди n+2 натуральных чисел также можно найти два числа, разность которых кратна числу n.

Рассмотрим n+2 натуральных чисел: a₁, a₂, ..., a_(n+1), a_(n+2).
Возможны два случая:

Случай 1: Среди первых n+1 чисел найдутся два числа, разность которых кратна числу n.
В этом случае доказательство уже выполнено.

Случай 2: В первых n+1 числах нет двух чисел, разность которых кратна числу n.
Рассмотрим последние два числа - a_(n+1) и a_(n+2).
Разность между этими числами равна a_(n+2) - a_(n+1).

Рассмотрим кратность этой разности числу n.
Если a_(n+2) - a_(n+1) делится на n, то мы доказали утверждение для этого случая.
Если a_(n+2) - a_(n+1) не делится на n, тогда рассмотрим число r = (a_(n+2) - a_(n+1)) mod n.
По определению остатка от деления, 0 <= r < n.

Заметим, что r представляет собой остаток от деления разности двух чисел на натуральное число n.
То есть, r = (a_(n+2) - a_(n+1)) mod n = a mod n - b mod n, где a и b - числа, соответствующие остаткам от деления a_(n+2) и a_(n+1) на n.

Так как существует всего n возможных остатков от деления на n (от 0 до n-1) и рассматриваемые нами числа не принимают одинаковых остатков от деления на n,
это означает, что по крайней мере один из остатков a mod n или b mod n должен быть равен n. Значит, их разность (a mod n - b mod n) должна быть кратна n.

Таким образом, для случая 2 мы также доказали утверждение.

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