Вопрос школьника
Ответь развернуто и подробно на вопрос — Дано 12 натуральних чисел. Доведіть, що з них завжди можна обрати два, різниця яких ділиться націло на 11
Ответ от учителя
Для того, чтобы доказать, что из 12 натуральных чисел всегда можно выбрать два, разность которых делится нацело на 11, нужно воспользоваться принципом Дирихле.
Принцип Дирихле утверждает, что если на $n$ объектов приходится больше чем $m$ различных меток, то хотя бы одна метка будет использована не менее чем $leftlceil frac{n}{m} rightrceil$ раз.
В данном случае мы имеем 12 чисел и 10 возможных остатков при делении на 11 (от 0 до 10). По принципу Дирихле, хотя бы один остаток должен встретиться не менее чем $leftlceil frac{12}{10} rightrceil = 2$ раза.
То есть, среди 12 чисел найдутся два, которые имеют одинаковый остаток при делении на 11. Разность этих чисел будет делиться нацело на 11.
Например, если среди 12 чисел есть 3 числа с остатком 0, 2 числа с остатком 1, 2 числа с остатком 2, 1 число с остатком 3, 1 число с остатком 4, 1 число с остатком 5, 1 число с остатком 6 и 1 число с остатком 7, то можно выбрать два числа с остатком 0 и их разность будет делиться нацело на 11.
Таким образом, мы доказали, что из 12 натуральных чисел всегда можно выбрать два, разность которых делится нацело на 11.
