Разбор задачи про пересаживание: принцип Дирихле

[ogn_slon]

На задававшую сложные задания учительницу
повторно завели уголовное дело.
    — заголовок новости

Итак, неделю назад была предложена следующая нехитрая задачка:

У круглого стола древнего культа расставлены десять стульев. Жребием выбирается пять «освященных» стульев, которые занимают пять жрецов по одному на стул, а другие пять стульев остаются свободными. Через час жрецы встают, обходят стол по часовой стрелке на одно и то же число мест каждый и садятся снова, так что взаимное расположение жрецов не меняется. Величина сдвига (то есть число мест между старым и новым стулом, одинаковое для всех) определяется самими жрецами. Суть культа в том, что после пересадки минимум три освященных стула должны остаться занятыми, иначе наступит конец света. Докажите, что при всякой исходной рассадке жрецы смогут пересесть так, чтобы избежать конца света.

Доказательство. Последовательность попарных расстояний по часовой стрелке между пятью освященными стульями начиная с любого из них состоит из 20 элементов (5×4), каждый из которых есть натуральное число от 1 до 9. Поскольку 20/9 > 2, хотя бы одно из чисел должно повторяться в последовательности минимум трижды. По построению, при пересадке на такое повторяющееся число мест как минимум три освященных стула останутся занятыми, что и требовалось доказать.

Это рассуждение демонстрирует известный «принцип Дирихле», который применительно к предложенной задаче можно озвучить так: при рассаживании 20 голубей по 9 клеткам хотя бы в одной клетке окажется не меньше трех голубей. В общем виде, при разбиении конечного множества на группы обязательно найдется хотя бы одна группа с числом элементов не меньше среднего во всех группах. Принцип Дирихле по сути утверждает, что при разделении множества на части его элементам приходится кучковаться некоторым минимальным образом, как голубям в клетках, потому что иначе им просто некуда деться. Именно такое доказательство было сдано в первом из двух засчитанных ответов (efimpp). Во втором правильном ответе было построено не столь лаконичное, но тоже вполне корректное доказательство от противного (panda_pandus).

Задачка на принцип Дирихле о пересаживании за круглым столом была подсмотрена в замечательном научно-популярном журнале Quanta. Применения принципа Дирихле, разумеется, не ограничиваются арифметическими развлечениями для школьников. Вспомнилось, что однажды коллега xmyruj, популяризовывая так называемую «теорему о бутерброде», продемонстрировал одно ее любопытное следствие как раз рассаживанием голубей по клеткам, насколько я могу судить. Выглядит вроде бы элементарно — но только после того, как объяснят.


Image credit: Olena Shmahalo/Quanta Magazine.