Теории всего на свете - Коллектив авторов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще кое-что о принципе голубей и ящиков

Чарлз Сейфе

Профессор журналистики Нью-Йоркского университета, бывший автор журнала Science; автор книги Proofiness: The Dark Arts of Mathematical Deception («Непроницаемость: темное искусство математического обмана»)

Порой даже простой подсчет может поведать нечто значительное. Однажды, еще в конце 1990‑х, будучи корреспондентом журнала New Scientist, я получил рекламное электронное письмо, воспевавшее какую-то необычайную компьютерную программу. В письме провозглашалось, что эта программа архивирования данных произведет настоящую революцию в цифровом мире, ибо она столь эффективна, что может сжать любой файл на 95 % или больше, не потеряв при этом ни единого бита данных. Может быть, мой журнал не упустит шанс поведать миру об этом софте, который позволит хранить на жестком диске в 20 раз больше информации, чем раньше?

Нет, мой журнал не станет об этом рассказывать, решил я.

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

Принцип голубей и ящиков – по сути, простое правило счета. Если у вас имеется n голубей и вам удалось запихнуть их менее чем в n ящиков, это означает, что по меньшей мере один ящик будет содержать в себе более одной птицы. Очевидно до банальности, не правда ли? Однако этот принцип – весьма полезный и мощный инструмент. К примеру, представим себе, что компрессионный софт, о котором шла речь, соответствует рекламному описанию и сжимает каждый файл в 20 раз без потери информации. Таким образом, каждый файл размером 2000 бит будет стиснут в какие-нибудь 100 бит, а при обращении алгоритма этот стобитный файл примет первоначальную форму, ничуть при этом не пострадав.