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

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

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

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

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

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

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

Минотавр

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

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

Судоку состоит из сетки 9 × 9, один квадрат состоит из меньшей сетки 3 × 3. В каждом квадрате игрок должен заполнить клетки цифрами от 1 до 9 так, что каждое число появляется только один раз в ряду и колонке всего большого квадрата. Кроме того, каждое число должно появляться один раз в каждом квадрате 3 × 3. Создатель головоломки раскидывает несколько цифр в квадрате, они являются подсказками, которые помогают игроку решить задачу. Еще одной особенностью судоку является то, что у каждой головоломки есть только одно решение.

Группа математиков во главе с Гэри МакГуайром из Дублинского университетского колледжа обнаружила, что минимальное количество подсказок, нужное для уникального – то есть единственного – решения, равно 17. Если в головоломке меньше подсказок, то у нее не может быть уникального решения. Однако МакГуайр и его команда не смогли найти этому доказательства. Вместо этого они использовали грубую вычислительную мощность для поиска по всем возможным сеткам судоку. На самом деле, они потратили 7 миллионов часов вычислительного времени в Дублинском центре высокопроизводительных вычислений. Им была необходима вся компьютерная мощность, которую они могли использовать, так как число возможных раскладок судоку огромно: 6 670 903 752 021 072 936 960. Однако исследователям удалось уменьшить это число до более приемлемого размера с помощью алгоритма, основанного на принципе, что некоторые раскладки математически эквивалентны.

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

NP– полная задача

В 2002 году математики утвердили, что судоку является NP-полной задачей. (NP – недетерминированное полиномиальное время.) Что это значит? В сущности, не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным. NP время очень длительное. Что это значит для судоку? Что не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным.