Доказать, что из любых 11 чисел всегда можно выбрать два таких числа, разность которых кратна 10.

Привет! Давай докажем это утверждение. Это классическая задача, которая решается с помощью принципа Дирихле.

Что такое принцип Дирихле?

Если у нас есть n «голубей» и m «клеток», причем n > m, то хотя бы в одной клетке окажется больше одного голубя. Проще говоря, если чего-то больше, чем мест, куда его можно положить, то хотя бы одно место будет занято дважды.

Применяем к нашей задаче:

1. «Голуби» — это 11 чисел, которые мы берем. (n = 11)

2. «Клетки» — это возможные остатки от деления числа на 10. Когда мы делим любое целое число на 10, остаток может быть одним из следующих:

• 0
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

Всего таких остатков 10. Это наши «клетки». (m = 10)

3. Сравнение: У нас 11 чисел (голубей) и 10 возможных остатков (клеток). Так как 11 > 10, то по принципу Дирихле обязательно найдется хотя бы один остаток, который встречается у двух (или более) чисел из наших 11.

4. Вывод: Пусть мы выбрали два числа, например, a и b, у которых одинаковый остаток при делении на 10. Это значит:

• a = 10*k₁ + r
• b = 10*k₂ + r

где r — это одинаковый остаток, а k₁ и k₂ — какие-то целые числа.

Теперь найдем разность этих чисел:

a - b = (10*k₁ + r) - (10*k₂ + r)

a - b = 10*k₁ + r - 10*k₂ - r

a - b = 10*k₁ - 10*k₂

a - b = 10 * (k₁ - k₂)

Полученное выражение 10 * (k₁ - k₂) означает, что разность чисел a и b делится на 10 без остатка, то есть кратна 10.

Утверждение доказано!