Отелло – это игра, чем-то напоминающая Го, ее изобрели в 1880-х два англичанина, изначально она называлась Реверси, хотя игры имеют достаточные различия. В обеих играх игроки окружают камни противника, в Отелло окруженные камни, черные с одной стороны и белые с другой, переворачиваются. В Го окруженные камни остаются того же цвета. Кроме того, доска в Отелло имеет разлиновку 8 × 8, что куда меньше, чем 19×19 в Го.
3.5. Шахматная доска и пшеница
Математическое понятие: геометрическая прогрессия
Существует история, согласно которой визирь при дворе короля Ширхама в Индии Сисса Бен Дахир изобрел игру в шахматы. Довольный изобретением Дахира король Ширхам предложил ему выбрать в качестве дара то, что он захочет. Сисса Бен Дахир попросил, казалось бы, безобидный дар: одно зерно пшеницы за первый квадрат шахматной доски, два за второй, четыре за третий и так далее, каждый последующий квадрат получал в два раза больше зерна, чем предыдущий. Мы можем представить этот процесс в виде суммирования: 20 + 21 + 22 + 23 +… 263. (Мы остановились на 63, так как, хоть и на доске 64 квадрата, степень первой 2 равна 0, а не 1.) Такое суммирование, где число остается неизменным, а степень растет с каждым шагом прогрессии, называется геометрической прогрессией. И хоть и кажется, что сумма будет не такой уж большой, она на самом деле будет огромной. На деле это число будет равно числу шагов, которые необходимы, чтобы решить задачу Ханойской башни, то есть 18 446 744 073 709 551 615 (см. главу 3.4). Если предположить, что в тонне пшеницы примерно 100 миллионов зерен, Сисса Бен Дахир попросил примерно 200 миллиардов тонн пшеницы. Действительно ошеломительное количество.
Шахматы с острова ЛьюисСамая впечатляющая коллекция шахмат в мире известна как шахматы с острова Льюис. Она состоит из 93 фигур XII века, которые были обнаружены в 1831 году на шотландском острове Льюис (Внешние Гебриды). Они изготовлены из моржовых костей и зубов китов, и кажется, что они имеют скандинавские корни: ладьи выполнены в форме солдат, кусающих свои щиты, как это делали берсерки.
3.6. Ханойская башня
Математические понятия: рекурсия, геометрическая прогрессия
Иногда простые правила могут привести к удивительно большим числам. Представьте Ханойскую башню, игрушку, состоящую из трех стержней, установленных вертикально на устойчивой базе, и стопки деревянных колец – у каждого отверстие в центре, – нанизанной на один стержень. Каждый диск разного размера, и они сложены так, что самый маленький диск лежит сверху и, по мере возрастания, самый большой лежит снизу. Целью игры является переместить стопку дисков на другой стержень так, чтобы диски лежали в том же порядке, но вы можете передвигать только один диск за раз, и нельзя класть больший диск на меньший.
Шаги, необходимые для достижения цели, являются примером рекурсии. Передвижение первого диска требует одного хода, но каждый последующий диск требует в два раза больше ходов, чем предыдущий. Если дисков много, то количество ходов для решения головоломки непостижимо велико. Например, существует легенда о Ханойской башне. Согласно этой легенде, в Индии есть Ханойская башня с тремя алмазными иглами, и на одной из них находятся 64 золотых диска, каждый меньше чем тот, что под ним. Монахи Брахмы следят за дисками, и постоянно один из монахов переставляет диски на другую иглу, согласно тем простым правилам, которые были упомянуты ранее.
Как долго они будут выполнять эту задачу? Если каждый ход занимает 1 секунду, и монахи не делают перерывов, то перестановка стопки дисков займет 18 446 744 073 709 551 615 секунд, что равно 58 триллионам лет, это намного больше, чем текущий возраст Вселенной (которой примерно всего 13 триллионов лет). Огромные числа действительно могут содержаться в простых вещах.
Ханойская башня в поп-культуреХанойская башня очень популярна в поп-культуре. В 1966 году в серии «Доктора Кто» Небесный игрушечник заставил Доктора сыграть в эту игру с 10 кольцами за ограниченное количество ходов (1023), он назвал ее Трилогической игрой. В 2011 году в фильме «Восстание планеты обезьян» эта головоломка, которую назвали Башней Лукаса, была использована для проверки интеллекта у обезьян.
3.7. Принцип голубей и ящиков
Математические понятия: принцип голубей и ящиков, комбинаторика
Никогда не сбрасывайте со счетов простую идею, так как такие идеи иногда имеют большие последствия. Одной из таких идей является принцип голубей и ящиков, который впервые сформулировал немецкий математик Петер Густав Лежен Дирихле в 1834 году. Согласно этому принципу, если у вас есть три ящика и четыре голубя, и каждый голубь должен занять ящик, следовательно, в одном ящике должно быть больше одного голубя. (Принцип не говорит, сколько голубей находится в каждом ящике или что в каждом ящике находится голубь. Все четыре голубя могут находиться в одном ящике, а два остальных останутся пустыми.) Если мы захотим описать этот принцип в более общей форме, не ссылаясь конкретно на голубей (принцип также работает и с коровами, индейками, футбольными мячами или любыми другими объектами), то можно сказать, что если у нас есть Н контейнеров и М объектов и М превышает количество Н, тогда в одном из контейнеров будет как минимум один объект.
Вы можете использовать принцип голубей и ящиков для заявлений о мире. Допустим, что у вас есть пачка M&M’s, половина конфет красные, а другая половина – коричневые. Какое минимальное количество конфет вам нужно вытащить из пачки, чтобы у вас было как минимум две конфеты одного цвета? (Ответ: 3. Вы можете выбрать две конфеты одинакового цвета в самом начале. Но вы также можете выбрать одну красную и одну коричневую. В этом случае цвет третьей конфеты будет уже не важен – у вас будет пара. В таком же ключе представьте две коробки: одна для красных конфет, другая – для коричневых. Мы хотим найти минимальное количество конфет, которые мы должны вытащить из пачки, чтобы две из них оказались в одной коробке.)
Этот принцип можно использовать и чтобы определить, что два человека в Нью-Йорке имеют одинаковое количество волос на голове. У каждого человека примерно 100 000 волос на голове, а в Нью-Йорке живут примерно 8 миллионов человек. Так как существует 100 000 вероятностей количества волос на любой человеческой голове, тогда, скажем, что у нас есть 100000 ящиков. А 8 миллионов жителей Нью-Йорка соответствуют 8 миллионам голубей, следовательно, мы можем быть уверенными, что как минимум два голубя – или человека – занимают одну коробку, то есть у них одинаковое количество волос на голове.
По-английски принцип голубей и ящиков звучит как «pigeonhole principle», но иногда слово «pigeonhole» используется в контексте без ссылок на голубей и контейнеры. В Конгрессе используют словосочетание «to pigeonhole a bill», что значит «отложить законопроект в долгий ящик», грубо говоря, положить его на полку и на время о нем забыть.
3.8. Лабиринты
Математические понятия: теория графов, топология
Лабиринты давно являются частью поп-культуры, начиная от мифов о Тесее и Минотавре и заканчивая медитативными церковными лабиринтами Средневековья; от кукурузных лабиринтов, которые появляются в сельской местности осенью, до фильмов «Лабиринт» и «Бегущий в лабиринте». Но в то время, как они интригуют своей красотой, они еще являются частью семьи математических объектов.
Изучением лабиринтов занимаются теория графов и топология, разделы, которые рассматривают объекты схематически (похоже на анализ метро в главе 1.9). Если вы подумаете о лабиринте абстрактно, не размышляя о поворотах, которые вам придется делать, или о высоте стен или текстуре земли под ногами, вы увидите его как путь, который на определенном моменте сворачивает в новом направлении. Каждую такую точку мы можем назвать узлом. Дорога, соединяющая два узла друг с другом, называется ребром. Если мы посмотрим на лабиринт сверху, мы можем сделать рисунок, своего рода диаграмму, состоящую из узлов и ребер. После разметки всех узлов мы смогли бы увидеть путь, который привел бы нас к концу лабиринта.
Этот вид анализа впервые был проведен Леонардом Эйлером, швейцарским математиком, который жил в 1700-х. Он решил проблему, известную как Семь мостов Кенигсберга, и тем самым основал раздел теории графов. Проблема была основана на реальном городе Кенигсберг в Пруссии. Река Преголя протекала через город, а посреди реки был остров. После того как река проходила мимо острова, она разделялась на две части. Семь мостов соединяли остров с материком, и местные жители интересовались, можно ли пересечь каждый мост только один раз и вернуться в исходную точку, не пройдя ни по одному из них дважды. Представив мосты, остров и материк как абстрактную сеть, состоящую из узлов и ребер, Эйлер доказал, что такого пути не существует.
Этот вид анализа впервые был проведен Леонардом Эйлером, швейцарским математиком, который жил в 1700-х. Он решил проблему, известную как Семь мостов Кенигсберга, и тем самым основал раздел теории графов. Проблема была основана на реальном городе Кенигсберг в Пруссии. Река Преголя протекала через город, а посреди реки был остров. После того как река проходила мимо острова, она разделялась на две части. Семь мостов соединяли остров с материком, и местные жители интересовались, можно ли пересечь каждый мост только один раз и вернуться в исходную точку, не пройдя ни по одному из них дважды. Представив мосты, остров и материк как абстрактную сеть, состоящую из узлов и ребер, Эйлер доказал, что такого пути не существует.
МинотаврВ лабиринте есть только одна дорога, ведущая от входа напрямую до центра. Говорят, что один известный лабиринт был построен по приказу царя Миноса под Кносским дворцом примерно 3000 лет назад на острове Крит. Согласно легенде, царь Минос построил лабиринт, чтобы заточить Минотавра, существо, рожденное от союза царицы и быка. Минос приказал жителям Афин присылать ему семь молодых мужчин и женщин каждый год, которых потом помещали в лабиринт на съедение Минотавру. Тесей решил положить конец этой ужасной традиции. Он вызвался добровольцем, и когда они все предстали перед царем, дочь царя Ариадна влюбилась в Тесея. Она дала ему клубок нити, чтобы он смог найти дорогу назад. Тесей убил Минотавра и выбрался из лабиринта, но по дороге назад в Афины он забыл поменять черные паруса на белые, так как это был знак отцу, что он выжил в схватке с Минотавром. Отец Тесея Эгей увидел четыре паруса и, сраженный печалью, бросился в океан.
3.9. Сколько подсказок вам понадобится, чтобы разгадать головоломку Судоку?
Математическое понятие: числовые головоломки
Судоку – это, возможно, одна из самых наших любимых головоломок, но это не просто способ убить несколько свободных секунд (или часов). Затягивающая числовая головоломка также содержит в себе некоторые интересные математические крупицы.
Судоку состоит из сетки 9 × 9, один квадрат состоит из меньшей сетки 3 × 3. В каждом квадрате игрок должен заполнить клетки цифрами от 1 до 9 так, что каждое число появляется только один раз в ряду и колонке всего большого квадрата. Кроме того, каждое число должно появляться один раз в каждом квадрате 3 × 3. Создатель головоломки раскидывает несколько цифр в квадрате, они являются подсказками, которые помогают игроку решить задачу. Еще одной особенностью судоку является то, что у каждой головоломки есть только одно решение.
Группа математиков во главе с Гэри МакГуайром из Дублинского университетского колледжа обнаружила, что минимальное количество подсказок, нужное для уникального – то есть единственного – решения, равно 17. Если в головоломке меньше подсказок, то у нее не может быть уникального решения. Однако МакГуайр и его команда не смогли найти этому доказательства. Вместо этого они использовали грубую вычислительную мощность для поиска по всем возможным сеткам судоку. На самом деле, они потратили 7 миллионов часов вычислительного времени в Дублинском центре высокопроизводительных вычислений. Им была необходима вся компьютерная мощность, которую они могли использовать, так как число возможных раскладок судоку огромно: 6 670 903 752 021 072 936 960. Однако исследователям удалось уменьшить это число до более приемлемого размера с помощью алгоритма, основанного на принципе, что некоторые раскладки математически эквивалентны.
Все это показывает, что даже развлечение в вашей газете может содержать в себе интересную математику.
NP– полная задачаВ 2002 году математики утвердили, что судоку является NP-полной задачей. (NP – недетерминированное полиномиальное время.) Что это значит? В сущности, не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным. NP время очень длительное. Что это значит для судоку? Что не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным.
3.10. Математические примеры в работах Ван Гога
Математическое понятие: турбулентность
«Звездная ночь» – это одна из самых красивых и знаковых работ Ван Гога, но в последнее время она известна не только за свою красоту, но также за скрытую в ней математику.
Оказывается, закрученные узоры в «Звездной ночи», а также в «Пшеничном поле с воронами» и в «Дороге с кипарисом и звездой» (две другие картины Ван Гога) демонстрируют странное сходство с турбулентными потоками. Такой вид движения, как турбулентность, можно увидеть в речном водовороте или в дыме от костра. Турбулентность также возникает в движении жидкости в трубах, а из-за турбулентного перемешивания теплого и холодного воздуха в атмосфере мы иногда чувствуем, как самолет начинает трясти во время полета. Хотя турбулентность – понятие обычное, описать его с помощью математики крайне сложно. Чтобы это сделать, математики должны понять решение уравнения Навье-Стокса, сформулированное в 1800-х, оно описывает движения жидкостей. На самом деле, эти уравнения очень сложно решить. (Существует история с участием турбулентности и физика Вернера Гейзенберга. Когда у него поинтересовались, что бы он спросил у Бога, если бы представилась такая возможность, Гейзенберг сказал: «Когда я встречусь с Богом, я задам ему два вопроса: почему теория относительности? И почему турбулентность? Я, правда, думаю, что у него будет ответ на первый вопрос».)
Чтобы определить, совпадают ли узоры в «Звездной ночи» с характеристиками турбулентного потока, ученые исследовали яркость красок, оставленных кистями Ван Гога. Они изучили цифровую версию его картины и сравнили яркость пикселей в пределах изображения. Они обнаружили, что схема яркости соответствует уравнениям, сформулированным в 1940-х русским математиком Андреем Колмогоровым, когда он пытался понять турбулентность, используя статистику. Так что живописная манера Ван Гога действительно имеет глубокое значение.
Андрей КолмогоровАндрей Колмогоров родился в 1903 году и был сыном сельского исследователя. У Колмогорова были разные интересы: в математике, среди прочего, он изучал теорию вероятности, топологию и турбулентность. Он также посвятил себя изучению истории и реформированию образования в Советском Союзе. Он умер в 1987 году.
8.11. Почему пройти поперек комнаты – это математический подвиг для вас?
Математические понятия: апории Зенона, бесконечность, бесконечный ряд
Если вы сейчас сидите – встаньте и сделайте несколько шагов. Простое действие – передвижение из одной точки в другую – было предметом математических и философских размышлений более 2000 лет назад для Зенона Элейского. Зенон жил в Древней Греции предположительно во времена Сократа, хотя и не существует достоверных данных о его жизни. Зенон хорошо известен за разработку серии парадоксов, направленных на стимулирование нашего мышления о понятиях, какие мы можем иметь о мире, в котором живем. Парадоксы затрагивают понятия движения и времени и, следовательно, включают математические идеи о бесконечности.
Первая апория о движении представляет собой аргумент, согласно которому движение невозможно. Представим, что вы хотите дойти от кресла до двери. Для этого вы, естественно, должны сначала дойти до середины между двумя объектами. Но перед тем, как вы дойдете до этой точки, вы должны дойти до другой точки, той, что лежит между серединой и вашей исходной позицией (что равно 1/4 пути до двери). Поэтому, чтобы пройти любое расстояние, вам нужно преодолеть бесконечное число расстояний, а так как невозможно выполнить бесконечное количество заданий, апория утверждает, что вы никогда не дойдете до двери.
Этот парадокс существует на протяжении столетий, так как не ясно, как его опровергнуть. Так как парадокс опирается на понятие, что пространство состоит из бесконечного числа единиц, кажется, что парадокс был сформулирован, чтобы указать на проблемы этого предположения. Аристотель предложил своего рода решение, когда утверждал, что расстояние между двумя точками не содержит фактической бесконечности, а содержит потенциальную бесконечность.
Только недавно математикам удалось предложить другое решение. Расстояние, которое мы должны пройти до двери, может быть представлено как сходящийся ряд: 1/2 + 1/4 + 1/8 + 1/16 + 1/32… Математики показали, что, хотя этот ряд бесконечно длинный, он сходится к конечному числу: 1. На самом деле, понятие, что бесконечный ряд бесконечно маленьких частей сводится к конечному целому, формирует основу исчисления и позволяет вам вычислить площадь под кривой.