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

3.9. Сколько подсказок вам понадобится, чтобы разгадать головоломку Судоку?

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

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

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

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

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

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

Оказывается, закрученные узоры в «Звездной ночи», а также в «Пшеничном поле с воронами» и в «Дороге с кипарисом и звездой» (две другие картины Ван Гога) демонстрируют странное сходство с турбулентными потоками. Такой вид движения, как турбулентность, можно увидеть в речном водовороте или в дыме от костра. Турбулентность также возникает в движении жидкости в трубах, а из-за турбулентного перемешивания теплого и холодного воздуха в атмосфере мы иногда чувствуем, как самолет начинает трясти во время полета. Хотя турбулентность – понятие обычное, описать его с помощью математики крайне сложно. Чтобы это сделать, математики должны понять решение уравнения Навье-Стокса, сформулированное в 1800-х, оно описывает движения жидкостей. На самом деле, эти уравнения очень сложно решить. (Существует история с участием турбулентности и физика Вернера Гейзенберга. Когда у него поинтересовались, что бы он спросил у Бога, если бы представилась такая возможность, Гейзенберг сказал: «Когда я встречусь с Богом, я задам ему два вопроса: почему теория относительности? И почему турбулентность? Я, правда, думаю, что у него будет ответ на первый вопрос».)

Чтобы определить, совпадают ли узоры в «Звездной ночи» с характеристиками турбулентного потока, ученые исследовали яркость красок, оставленных кистями Ван Гога. Они изучили цифровую версию его картины и сравнили яркость пикселей в пределах изображения. Они обнаружили, что схема яркости соответствует уравнениям, сформулированным в 1940-х русским математиком Андреем Колмогоровым, когда он пытался понять турбулентность, используя статистику. Так что живописная манера Ван Гога действительно имеет глубокое значение.

Андрей Колмогоров родился в 1903 году и был сыном сельского исследователя. У Колмогорова были разные интересы: в математике, среди прочего, он изучал теорию вероятности, топологию и турбулентность. Он также посвятил себя изучению истории и реформированию образования в Советском Союзе. Он умер в 1987 году.

Если вы сейчас сидите – встаньте и сделайте несколько шагов. Простое действие – передвижение из одной точки в другую – было предметом математических и философских размышлений более 2000 лет назад для Зенона Элейского. Зенон жил в Древней Греции предположительно во времена Сократа, хотя и не существует достоверных данных о его жизни. Зенон хорошо известен за разработку серии парадоксов, направленных на стимулирование нашего мышления о понятиях, какие мы можем иметь о мире, в котором живем. Парадоксы затрагивают понятия движения и времени и, следовательно, включают математические идеи о бесконечности.

Первая апория о движении представляет собой аргумент, согласно которому движение невозможно. Представим, что вы хотите дойти от кресла до двери. Для этого вы, естественно, должны сначала дойти до середины между двумя объектами. Но перед тем, как вы дойдете до этой точки, вы должны дойти до другой точки, той, что лежит между серединой и вашей исходной позицией (что равно 1/4 пути до двери). Поэтому, чтобы пройти любое расстояние, вам нужно преодолеть бесконечное число расстояний, а так как невозможно выполнить бесконечное количество заданий, апория утверждает, что вы никогда не дойдете до двери.

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

Только недавно математикам удалось предложить другое решение. Расстояние, которое мы должны пройти до двери, может быть представлено как сходящийся ряд: 1/2 + 1/4 + 1/8 + 1/16 + 1/32… Математики показали, что, хотя этот ряд бесконечно длинный, он сходится к конечному числу: 1. На самом деле, понятие, что бесконечный ряд бесконечно маленьких частей сводится к конечному целому, формирует основу исчисления и позволяет вам вычислить площадь под кривой.

Теперь, когда пойдете к двери, вы можете оценить вековые математические рассуждения под ногами!

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

Время от времени находится какой-нибудь математик, который меняет ход истории. Одним из них был Клод Шеннон. В середине ХХ века Шеннон работал в Bell Labs (знаменитый исследовательский отдел AT&T), потом преподавал в Массачусетском технологическом институте. Он также был инженером по электронике и интересовался коммуникациями. Его исследование положило начало теории информации, благодаря которой появились цифровые компьютеры, Интернет и компакт-диски. Он также помог популяризировать термин «бит», что является сокращением от «двоичной цифры». Другими словами, Шеннон сделал будущее возможным.

Одна из идей пришла к Шеннону, когда он учился в магистратуре в Массачусетском технологическом институте. Он понял, что структура коммутационной схемы в аналоговых компьютерах и телефонных сетях напоминала структуру булевой алгебры (см. главу 3.19). В физическом смысле замкнутая цепь могла представлять логическое значение «истина», а открытая цепь – «ложь». В сущности, Шеннон понял, что можно записать работу логики в машине. Вы на самом деле можете решить проблему по логике и математике, используя переключатели и цепи. Это вылилось в магистерскую диссертацию Шеннона в 1938 году под названием «Символьный анализ реле и коммутаторов», теперь эту диссертацию называют самой важной диссертацией ХХ века.