В некоторых олимпиадных задачах требуется доказать, что нужная группа обязательно найдётся, хотя сами числа заранее неизвестны. Здесь может помочь принцип Дирихле: вместо перебора чисел мы распределяем их по небольшому числу групп. Разберём собственное учебное упражнение, не приписывая его официальному туру.
Условие, которое не требует знать сами числа
Выбраны тринадцать различных натуральных чисел. Докажем, что среди них можно найти три, у которых разность любых двух делится на шесть. Числа не обязаны идти подряд, быть небольшими или укладываться в определённый промежуток.
Сразу искать подходящие разности неудобно: без списка чисел вычислять нечего. Поэтому спросим иначе: какой признак двух чисел гарантирует делимость их разности на шесть?
Сделаем шесть групп
Каждое натуральное число при делении на шесть имеет ровно один остаток: 0, 1, 2, 3, 4 или 5. Распределим выбранные числа по этим остаткам. Получается шесть групп, причём ни одно число не пропущено и ни одно не попало сразу в две группы.
Если бы в каждой группе оказалось не больше двух чисел, всего удалось бы разместить не больше 6 × 2 = 12 чисел. Но у нас их тринадцать. Значит, хотя бы одна группа содержит не менее трёх. Это применение обобщённого принципа Дирихле, изложенного в первой лекции курса MIT 18.200.
Вернёмся от групп к требованию задачи
Три найденных числа имеют общий остаток r. Запишем их как 6a + r, 6b + r и 6c + r. Разность первых двух равна 6(a − b), первых и третьих — 6(a − c), вторых и третьих — 6(b − c). Каждая разность делится на шесть.
В этом переходе важно слово «любых». Мы получили не одну удачную пару, а тройку с нужным свойством для всех трёх пар. При вычитании большего числа из меньшего разность будет отрицательной, но это не мешает ей быть целым кратным шести.
Почему число тринадцать выбрано точно
Можно ли гарантировать такую тройку уже среди двенадцати различных натуральных чисел? Возьмём числа от 1 до 12. В каждой из шести групп остатков будет ровно два числа: например, остаток 1 имеют 1 и 7, остаток 0 — 6 и 12. Тройки с одним остатком нет.
Для нашей задачи совпадение остатков не просто удобный признак. Если разность двух чисел делится на шесть, их остатки при делении на шесть совпадают. Разность остатков лежит от −5 до 5; единственное кратное шести в этих границах — нуль. Поэтому в наборе от 1 до 12 нет и требуемой тройки. Тринадцать — минимальное количество для гарантии при любом выборе.
Это не означает, что отдельная короткая выборка не может подойти: числа 1, 7 и 13 уже образуют нужную тройку. Различайте существование в конкретном наборе и гарантию для каждого набора заданного размера.
При самостоятельном решении запишите три вещи: что распределяется, сколько групп и почему каждый объект получает одну группу. Затем обязательно свяжите найденное совпадение с исходным требованием. Сам принцип обнаруживает тесную группу; математический смысл выбранного признака завершает доказательство.
