Принцип голубей и ящиков

Джон Клейнберг

Тишевский профессор информатики Корнелльского университета (участник программы Тишевской школы искусств Нью-Йоркского университета); автор книги Networks, Crowds and Markets: Reasoning About a Highly Connected World («Сети, толпы и рынки. Рассуждения о чрезвычайно взаимосвязанном мире») (совместно с Дэвидом Изли)

Некоторые математические факты создают такое впечатление, будто содержат в себе какую-то спрессованную силу. Поначалу, при первом знакомстве, они выглядят невинно, однако кажутся ошеломляющими, когда вы наблюдаете их в действии. Один из самых потрясающих примеров – так называемый принцип голубей и ящиков (принцип Дирихле).

Вот в чем его суть. Предположим, стая голубей садится на группу деревьев, причем голубей больше, чем деревьев. Тогда после того, как все голуби опустятся на ветки, по меньшей мере на одном из деревьев окажется больше двух голубей. [О «ящиках» в названии идет речь, так как они часто фигурируют в описании принципа вместо деревьев.]

Этот принцип кажется очевидным, каковым он и является. Голубей попросту слишком много, так что каждый из них не может иметь собственное дерево. Если бы история на этом и кончалась, непонятно было бы, отчего столь тривиальный факт заслужил такое внимание. Но чтобы по-настоящему оценить сей голубиный принцип, не помешает ознакомиться с некоторыми вещами, которые можно проделывать с его помощью.

Давайте перейдем к гораздо менее самоочевидному факту. Само по себе утверждение, которое мы сейчас приведем, весьма интригующе, однако еще более интригует та легкость, с которой оно выводится из принципа голубей и ящиков. Вот вам факт: на вашем фамильном древе (будем рассматривать лишь его участок, отвечающий последним четырем тысячам лет) есть два человека, назовем их А и В, причем А является предком матери В и одновременно предком отца В. Иными словами, на вашем фамильном древе имеется своего рода петля: две ветки, растущие вверх от В, сходятся к А, то есть среди ваших предков есть родительская пара, состоящая из кровных родственников – благодаря их сравнительно недавнему общему предку А.

Здесь следует упомянуть о некоторых важных вещах. Во-первых, «вы» из предыдущего параграфа – это именно вы, читатель. Да, одно из любопытных свойств приведенного факта состоит именно в том, что я могу сделать такое утверждение, даже не зная, кто вы. Во-вторых, это утверждение не основывается ни на каких предположениях насчет человечества как биологической общности или географических превратностей его истории. Вот все допущения, которые мне нужны:

1. У каждого человека двое биологических родителей.

2. Ни у кого не появляются дети после 100 лет.

3. Человечеству не менее 4 тысяч лет.

4. За последние 4 тысячи лет на Земле жило в общей сложности не больше триллиона человеческих существ. (На самом деле ученые предполагают, что за всю историю человечества на Земле существовало, по приблизительным оценкам, около 100 миллиардов человек. Я на всякий случай увеличил эту оценку на порядок.)

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

Вернемся к вам и вашим пращурам. Начнем рисовать ваше генеалогическое древо на 40 поколений в прошлое: вы, ваши родители, их родители и т. п., на 40 шагов назад. Поскольку каждое поколение, как правило, живет не больше 100 лет, последние 40 поколений на вашем фамильном древе все разместятся в прошедших четырех тысячах лет. (Собственно, они почти наверняка займут всего 1000–1200 лет, но помните, что мы всеми силами стараемся избежать возможных внутренних противоречий.)

Создание вашего генеалогического древа можно уподобить вычерчиванию «организационной схемы» – скажем, когда требуется отыскать людей для определенного набора профессий или ролей. Иными словами, кто-то должен быть вашей матерью, кто-то должен быть вашим отцом, кто-то должен быть отцом вашей матери и т. п., восходя вверх по древу. Каждую из этих позиций назовем «ролью предка»: это своего рода профессия, существующая в вашей генеалогической схеме, и мы можем говорить о работе вне зависимости от того, кто ее выполняет. При движении вверх (в прошлое) по вашему фамильному древу первое поколение над вами имеет две роли предка, соответствующие двум вашим родителям. Второе поколение содержит четыре роли предка (две ваших бабушки и два ваших дедушки), третье – восемь ролей (все ваши прабабушки и прадедушки). При подъеме на каждый следующий уровень удваивается число ролей предков (вакансий, которые необходимо заполнить). Расчеты показывают, что 40 поколений потребуют более триллиона ролей, и для каждой должен существовать исполнитель.

Тут-то и выходит на сцену принцип голубей и ящиков. Последние 40 поколений вашего генеалогического древа размещаются в последних четырех тысячах лет, а мы уже приняли как допущение, что в течение этого периода на Земле успел пожить триллион человек. А значит, ролей предков (таких ролей свыше триллиона) больше, чем людей, которые могли бы сыграть эти роли (таких людей не более триллиона). Что и подводит нас к решающему моменту рассуждения: по меньшей мере две роли среди ваших предков исполнял один и тот же человек. Назовем его (или ее) А.

Идентифицировав А таким способом, мы уже сделали основную часть работы. Теперь, начиная от двух различных ролей, которую А довелось сыграть среди ваших предков, давайте двинемся вниз по генеалогическому древу – в вашу сторону. Две линии, идущие вниз от А, должны впервые встретиться друг с другом в виде какой-то роли предка на более низком уровне древа. Эту роль исполняет В. Поскольку здесь эти две линии встречаются впервые, одна линия пришла к В через его (или ее) мать, а другая – через его (или ее) отца. Иными словами, А – предок матери В и одновременно предок отца В, что и требовалось доказать.

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

Во-вторых, у этого рассуждения имеется, как называют это математики, неконструктивный аспект. Оно вовсе не дает вам рецепта для отыскания А и В на вашем фамильном древе, оно лишь убеждает вас в том, что такие А и В должны на нем существовать – и, в общем-то, не более того.

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