Рафаель Роузен - Математика для гиков

Как долго они будут выполнять эту задачу? Если каждый ход занимает 1 секунду, и монахи не делают перерывов, то перестановка стопки дисков займет 18 446 744 073 709 551 615 секунд, что равно 58 триллионам лет, это намного больше, чем текущий возраст Вселенной (которой примерно всего 13 триллионов лет). Огромные числа действительно могут содержаться в простых вещах.

Ханойская башня очень популярна в поп-культуре. В 1966 году в серии «Доктора Кто» Небесный игрушечник заставил Доктора сыграть в эту игру с 10 кольцами за ограниченное количество ходов (1023), он назвал ее Трилогической игрой. В 2011 году в фильме «Восстание планеты обезьян» эта головоломка, которую назвали Башней Лукаса, была использована для проверки интеллекта у обезьян.

Никогда не сбрасывайте со счетов простую идею, так как такие идеи иногда имеют большие последствия. Одной из таких идей является принцип голубей и ящиков, который впервые сформулировал немецкий математик Петер Густав Лежен Дирихле в 1834 году. Согласно этому принципу, если у вас есть три ящика и четыре голубя, и каждый голубь должен занять ящик, следовательно, в одном ящике должно быть больше одного голубя. (Принцип не говорит, сколько голубей находится в каждом ящике или что в каждом ящике находится голубь. Все четыре голубя могут находиться в одном ящике, а два остальных останутся пустыми.) Если мы захотим описать этот принцип в более общей форме, не ссылаясь конкретно на голубей (принцип также работает и с коровами, индейками, футбольными мячами или любыми другими объектами), то можно сказать, что если у нас есть Н контейнеров и М объектов и М превышает количество Н, тогда в одном из контейнеров будет как минимум один объект.

Вы можете использовать принцип голубей и ящиков для заявлений о мире. Допустим, что у вас есть пачка M&M’s, половина конфет красные, а другая половина – коричневые. Какое минимальное количество конфет вам нужно вытащить из пачки, чтобы у вас было как минимум две конфеты одного цвета? (Ответ: 3. Вы можете выбрать две конфеты одинакового цвета в самом начале. Но вы также можете выбрать одну красную и одну коричневую. В этом случае цвет третьей конфеты будет уже не важен – у вас будет пара. В таком же ключе представьте две коробки: одна для красных конфет, другая – для коричневых. Мы хотим найти минимальное количество конфет, которые мы должны вытащить из пачки, чтобы две из них оказались в одной коробке.)

Этот принцип можно использовать и чтобы определить, что два человека в Нью-Йорке имеют одинаковое количество волос на голове. У каждого человека примерно 100 000 волос на голове, а в Нью-Йорке живут примерно 8 миллионов человек. Так как существует 100 000 вероятностей количества волос на любой человеческой голове, тогда, скажем, что у нас есть 100000 ящиков. А 8 миллионов жителей Нью-Йорка соответствуют 8 миллионам голубей, следовательно, мы можем быть уверенными, что как минимум два голубя – или человека – занимают одну коробку, то есть у них одинаковое количество волос на голове.

По-английски принцип голубей и ящиков звучит как «pigeonhole principle», но иногда слово «pigeonhole» используется в контексте без ссылок на голубей и контейнеры. В Конгрессе используют словосочетание «to pigeonhole a bill», что значит «отложить законопроект в долгий ящик», грубо говоря, положить его на полку и на время о нем забыть.

Лабиринты давно являются частью поп-культуры, начиная от мифов о Тесее и Минотавре и заканчивая медитативными церковными лабиринтами Средневековья; от кукурузных лабиринтов, которые появляются в сельской местности осенью, до фильмов «Лабиринт» и «Бегущий в лабиринте». Но в то время, как они интригуют своей красотой, они еще являются частью семьи математических объектов.

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

Этот вид анализа впервые был проведен Леонардом Эйлером, швейцарским математиком, который жил в 1700-х. Он решил проблему, известную как Семь мостов Кенигсберга, и тем самым основал раздел теории графов. Проблема была основана на реальном городе Кенигсберг в Пруссии. Река Преголя протекала через город, а посреди реки был остров. После того как река проходила мимо острова, она разделялась на две части. Семь мостов соединяли остров с материком, и местные жители интересовались, можно ли пересечь каждый мост только один раз и вернуться в исходную точку, не пройдя ни по одному из них дважды. Представив мосты, остров и материк как абстрактную сеть, состоящую из узлов и ребер, Эйлер доказал, что такого пути не существует.

В лабиринте есть только одна дорога, ведущая от входа напрямую до центра. Говорят, что один известный лабиринт был построен по приказу царя Миноса под Кносским дворцом примерно 3000 лет назад на острове Крит. Согласно легенде, царь Минос построил лабиринт, чтобы заточить Минотавра, существо, рожденное от союза царицы и быка. Минос приказал жителям Афин присылать ему семь молодых мужчин и женщин каждый год, которых потом помещали в лабиринт на съедение Минотавру. Тесей решил положить конец этой ужасной традиции. Он вызвался добровольцем, и когда они все предстали перед царем, дочь царя Ариадна влюбилась в Тесея. Она дала ему клубок нити, чтобы он смог найти дорогу назад. Тесей убил Минотавра и выбрался из лабиринта, но по дороге назад в Афины он забыл поменять черные паруса на белые, так как это был знак отцу, что он выжил в схватке с Минотавром. Отец Тесея Эгей увидел четыре паруса и, сраженный печалью, бросился в океан.