Принцип Дирихле

Продолжаю рассматривать почти тривиальные принципы, потихоньку переходя к комбинаторике. Рассматриваемые сейчас темы достаточно скучные, но я постарался сделать их немного веселее чем обычно, вставив по возможности остроумные примеры.

С верткой pdf в этот раз приключилось что-то непонятное — изображения расползлись по разным страницам. То есть формально всё верно, но чтобы найти нужную картинку читателю иногда потребуется пролистать два-три листа. Если кто понимает как это править — просьба поспособствовать.

Все исходники как всегда на GitHub. Заодно добавил одну задачу в прошлый параграф о делимости (впрочем, когда-до давно она уже всплывала в моем блоге аж три года назад).

Предположим, что у нас есть клеток и голубь, и мы рассадили голубей по клеткам. Довольно очевидно, что в одной из клеток окажется по крайней мере два голубя. Впервые это тривиальные наблюдение сделал и начал использовать в математике немецкий математик Дирихле в XIX веке. С тех пор это наблюдение называется в России «прицнипом Дирихле», а за пределами бывшего СССР «принципом голубиных гнёзд» (pigeonhole principle). Прежде чем перейти к более сложным примерам применения этого принципа, переформулируем утверждение на языке множеств.

Теорема. Пусть и такие множества, что , и дана функция . Тогда функция не является инъективной.

Доказательство. Для инъективной функции , однако в нашем случае это противоречит условию , поскольку .

Упражнение. Утверждение принципа Дирихле тривиально в терминах множеств и отображений. А сможете ли вы доказать этот принцип, используя только аксиоматику Пеано?

Введем обозначение . Эта операция называется потолок и интуитивно представляет собой результат деления на с округлением в большую сторону: если число не делится без остатка, то к частному прибавляется единица.

Упражнение. Пусть теперь у нас голубей и клеток. Докажите, что в одной из клеток окажется по крайней мере голубей. Эта теорема называется обобщенным принципом Дирихле.

Рассмотрим теперь ряд простых применений принципа Дирихле. Частично они позаимствованы из Википедии, частично из замечательной книги «A Walk Through Combinatorics», частично просто выплыли из глубин памяти.

Пример. Пусть в ящике лежит большое число белых, черных и красных носков. Когда мы вытаскиваем носок, мы не видим его цвет до тех пор, пока не вытащим его. Cколько надо достать носков, прежде чем мы гарантированно получим пару одного цвета?

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

Упражнение. На праздник пришло человек. Какие-то из этих людей поздоровались за руку. Докажите, что всегда найдётся такая пара людей, которые совершили одинаковое число рукопожатий.

Данное утверждение называется «леммой о рукопожатиях» и может быть сформулировано более абстрактно для графов:

Определение. Степенью вершины графа называется число рёбер, инцидентных ей.

Лемма о рукопожатиях. В любом графе найдутся две вершины с одинаковой степенью.

Пример. Давайте докажем, что в Москве найдётся по крайней мере два человека с одинаковым числом волос на голове.

Пусть  — множество жителей Москвы,  — множество чисел, соответствующих возможному числу волос на голове. Точно мы это множество определить видимо не можем, но по крайней мере можем дать грубую оценку . Однако жителей Москвы явно больше. Опять же мы не знаем этого точно, но по крайней мере , откуда следует то отображение не может быть инъективным и найдутся два жителя с одинаковым числом волос.

Пример. Рассмотрим последовательность чисел 1, 11, 111, 1111, и докажем, что в этой последовательности найдётся число, которое делится на 123.

Вначале обозначим элементы этой последовательности как и заметим, что их можно записать как

Предположим теперь, что числа, которое делится на 123, в этой последовательности нет. Рассмотрим тогда последовательность остатков от деления на 123 элементов этой последовательности:

В этой последовательности обязательно найдутся два одинаковых числа, поскольку остаток от деления на 123 может максимум равняться 122, поэтому по принципу Дирихле уже среди первых 123 элементов мы встретим повторение. Пусть это будут остатки от деления чисел и на 123 (для определенности пусть ), которые мы обозначим за :


Вычтя из первого равенства второе имеем
\begin{equation}\label{np:1}
a_i - a_j = 123(q_i - q_j)
\end{equation}
Однако если вспомнить определение то легко увидеть, что
\begin{align*}
a_i - a_j &= \sum_{k=0}^{i-1}10^k - \sum_{k=0}^{j-1}10^k \\&= \sum_{k=j}^{i-1}10^k \\&= 10^j\sum_{k=0}^{i-j}10^k \\&= 10^j a_{i-j}
\end{align*}
Сопоставляя это с \eqref{np:1}, получаем

Здесь правая часть делится на 123, а значит на 123 должна делится и левая часть. Однако и взаимопросты и более того не делится на 123. Отсюда следует, что , что и требовалось.

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

У читателя есть отец и мать (2 человека). У них у каждого так же в свою очередь есть по отцу и матери — это дедушки и бабушки читателя, всего их человека. У них в свою очередь есть свои мамы и папы (прабабушки и прадедушки), которых всего человек. Легко увидеть закономерность: -е поколение предков читателя состоит из человек. Если грубо предположить, что поколения сменяются каждые 25 лет, то за 1000 лет поколения успели смениться 40 раз, и того за 1000 лет читатель имел

предков. Последнее равенство легко следует из свойств двоичной системы счисления (проверьте!).

В то же время население нашей планеты в данный момент меньше чем , а в прошлые года оно было еще меньше. Как самая грубая верхняя оценка количества людей живущих на земле в последнюю 1000 лет можно взять величину  — она намного выше реального количества людей, проживавших на земле, но однако даже эта оценка не превосходит величины , в чём легко убедиться, взяв в руки калькулятор.

Рассуждение будет понятнее, если посмотреть на генеалогическое дерево на рисунке 3.3.

Предположение о том, что это дерево будет ветвиться именно в таком виде всю тысячу лет противоречит принципу Дирихле: если бы это было так, то дерево имело бы куда больше узлов, нежели за 1000 лет жило людей на земле. А отсюда значит, что где-то наверху по крайней мере две ветви генеалогического дерева сомкнутся. А это ровно то, что требовалось доказать.

Пример. Мистер и миссис Смит пригласили к себе в гости четыре пары. Некоторые из приглашенных были друзьями мистера Смита, а некоторые друзьями миссис Смит. Когда гости прибыли, те, кто знали друг друга ранее, пожали руки. Когда всё это произошло, мистер Смит говорит: «Как интересно! Если не считать меня, то здесь никто не поздоровался за руку одинаковое количество раз». Вопрос: сколько раз пожала руку миссис Смит?

На первый взгляд задача кажется абсолютно нерешаемой. Тем не менее, проявив стойкость, мы можем её решить опять же с помощью всё того же принципа Дирихле. Начинает задача поддаваться решению, если мы изобразим её в виде графа.

Каждый человек на вечеринке у нас будет представлен отдельной вершиной. Ребра графа будут соответствовать рукопожатиям. Семейные пары будем выделять рамкой. На начальном этапе нам известно лишь, что все присутствующие кроме мистера Смита совершили различное количество рукопожатий. Максимальное количество рукопожатий, которые могло быть совершено — 8 (всего десять гостей, причем со своим спутником никто не здоровается, отсюда максимум восемь рукопожатий). Поэтому все вершины мы можем пронумеровать числами от 0 до 8, и одну вершину мы обозначим просто как Смит — мы не знаем сколько рукопожатий он совершил. Самих гостей мы будем нумеровать так же, то есть когда мы будем говорить фразу «пятый гость», то мы будем подразумевать гостя, который совершил пять рукопожатий. Получившийся граф представлен на рис. 3.4.

Рассмотрим поближе 8-го гостя. Он не поздоровался лишь с одним человеком с одной стороны, и с другой стороны он очевидно не здоровался со своим спутником. Так же мы знаем точно, что он не здоровался с нулевым гостем, так как нулевой гость не совершил вообще ни одного рукопожатия. Соответственно нулевой гость и есть его спутник. Со всеми остальными гостями он поздоровался. Полученный результат изображен на рисунке 3.5.

Теперь рассмотрим 7-го гостя. Он не поздоровался за руку с двумя гостями, один из которых — его партнёр, а вторым должен быть нулевой гость (нулевой гость не может быть партнёром 7-го гостя, так как мы уже выяснили, что нулевой и восьмой гости образуют пару). Глядя на граф мы так же видим, что первый гость поздоровался с восьмым гостем, но так как нам известно, что он в принципе поздоровался лишь с одним человеком, то он не мог поздороваться с седьмым гостем. Значит, первый и седьмой гости образуют пару, и седьмой гость поздоровался со всеми кроме нулевого и первого гостя. Это отображено на рисунке 3.6.

Совершенно аналогичным образом мы можем показать, что шестой гость не здоровался с гостями 0, 1 и 2, и что 2-ой гость является его спутником. Отсюда можно аналогично получить, что пятый гость не здоровался с гостями 0, 1, 2 и 3, и что третий гость является его спутником. Результат представлен на рисунке 3.7

Теперь мы нашли пару для всех людей, кроме четвертого. Единственная возможная пара для четвертого человека — это мистер Смит, поэтому четвертый человек и есть миссис Смит и она пожала руку ровно четырем людям.

Для последнего упражнения этого параграфа опять введём новую нотацию: будем обозначать через остаток от деления на .

Упражнение. Пусть и  — взаимопростые числа и пусть нам известно, что


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