Day #302

Математики рассказывают о задачах, которые не имеют положительного решения, но имеют принципиальное значение для понимания того, что такое математика.Записала Светлана Рейтер. Фотограф Грегори Т. Дэвис (Gregory T. Davis).

Проблема четырех красок

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

ВЛАДИМИР УСПЕНСКИЙ завкафедрой математической логики и теории алгоритмов механико-математического факультета МГУ:

«Сколько у нас стран на политической карте мира — что-то около двухсот, правильно? Найти такое количество разных красок непросто. Да и 50 красок для раскраски американских штатов найти не слишком легко — пусть даже Аляска и Гавайи ни с каким другим штатом не граничат. Правильной считается та раскраска карты, в которой административные регионы (страны, штаты, графства и тому подобное), имеющие общую границу — участок границы, а не просто уголок (как поля на шахматной доске), — красятся в разные цвета. И вот в середине XIX века в одной из британских картографических типографий резонно возник вопрос: «А сколько красок достаточно для правильного раскрашивания всех графств на карте Англии»? Сколько нужно иметь красок в типографии для печати административной карты — любого государства или даже Марса, если там тоже есть административное деление. Экспериментальным способом пришли к тому, что достаточно четырех красок. Доказательств в типографии не нашли, да, честно говоря, и не пытались найти, и обратились за помощью к математикам. В 1852 году на заседании Лондонского математического общества математиком Фрэнсисом Гатри был сделан доклад на эту тему. Через несколько лет сумели доказать, что пяти красок для раскрашивания любой административной карты точно хватает. Но остался вопрос о четырех красках. В том, что трех красок не хватает, легко может убедиться каждый. В 1976 году удалось доказать, что для раскраски любой административной карты вполне хватает четырех красок — иначе говоря, нет такой карты, для раскрашивания которой требовалось бы пять красок! Но к этому доказательству некоторые люди относятся скептически, поскольку для него потребовался компьютер. Где гарантия, что была безупречной программа, сквозь которую прогоняли все необходимые для доказательства карты?

Задача о четырех красках относится к самой элементарной ветви топологии, называемой «геометрией расположения». Это начало топологии, ее наглядная часть, поскольку современная топология гораздо более абстрактная и сложная, и не всякому студенту первого курса ее объяснишь. Задача же о четырех красках замечательна тем, что ее можно объяснить и первокласснику, и очень хочется нарисовать такую карту, для раскраски которой потребовалось бы пять цветов. Кстати, первоклассникам именно так и надо ставить задачу: не говорить им, что всегда достаточно четырех красок, а просить нарисовать карту, для которой четырех красок не хватает, и только спустя несколько дней сообщить, что это невозможно. Благодаря таким задачам любой человек с улицы сразу понимает, что математика очень элегантна. Ясное понимание несуществования чего-то — чисел ли с заданными свойствами, или способов построения геометрических фигур, или алгоритмов — создает особый дискурс, который можно было бы назвать культурой невозможного. И культура невозможного, и предпринимаемые математикой попытки познания бесконечного значительно расширяют горизонты мышления. Все это, ломая традиционный стереотип математики как сухой цифири, создает ее образ как живой области знания».

Проблема трех домов и трех колодцев

Проблема трех домов и трех колодцев

Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу? Дорожки не могут проходить через колодцы и домики.

СЕРГЕЙ СОПРУНОВ, старший научный сотрудник Вычислительного центра РАН:

«Это очень старая задача, и у меня к ней несколько личное отношение. Когда я учился математике и принес одну из первых своих статей своему учителю, Владимиру Андреевичу Успенскому, он посмотрел на утверждение, занимавшее примерно полстраницы и состоявшее более из формул, чем из слов, а потом сказал, что хороший математический результат должен выглядеть как задача о трех домах и трех колодцах. То есть формулировка должна быть понятна всем, а доказательство — ну, уж как получится. В некотором смысле задача о трех домах и трех колодцах является эталоном хорошего математического результата. Она имеет отрицательное решение и на плоскости, и на сферической поверхности — например, на глобусе. В доказательстве невозможности используется теорема Жордана — пример того, почему некоторые люди считают, что математики зря тратят деньги налогоплательщиков, придумывая строгие доказательства для таких истин, в которых не станет сомневаться ни один здравомыслящий человек. В данном случае теорема может быть сформулирована так: нарисуем на плоскости замкнутую линию, без самопересечений. Она разделит плоскость на две области: внутреннюю и внешнюю, а линия является границей этих двух областей. Любые две точки из одной и той же области можно соединить линией, не пересекающей нарисованную нами границу. Любая линия, соединяющая какие-либо две точки из разных областей, обязательно пересечет границу. Доказательство этой теоремы достаточно сложно, хотя большинство людей считают, что доказывать тут нечего, все и так очевидно. Поясним, какое отношение имеет теорема Жордана к трем домам и трем колодцам — здесь мы приводим просто правдоподобное рассуждение, а вовсе не строгое решение задачи. Пусть дорожки можно проложить. Давайте на минуту забудем про третий дом. Мы идем от первого дома к первому колодцу по проторенной тропинке, затем от первого колодца ко второму дому. Потом, для разнообразия, от второго дома ко второму колодцу, а дальше — от второго колодца к первому дому. Таким образом, мы получаем замкнутый путь без пересечений. По теореме Жордана, этот замкнутый путь разбивает нашу плоскость на две области. Давайте закрасим красным цветом ту область, в которой нет третьего колодца. Мы заметим, что до третьего колодца из красной области без пересечений границы не добраться. Теперь мы проводим путь от первого дома до третьего колодца и от третьего колодца ко второму дому. Он соединяет две точки границы, целиком лежит в незакрашенной области и делит эту область на две части. Одна часть ограничена путем через третий и первый колодцы, а вторая — путем через третий и второй колодцы. Ту часть, которая ограничена путем через первый и третий колодцы, мы закрасим синим; утверждается, что из синей области до второго колодца без пересечения границ не добраться. Оставшуюся область, ограниченную путем через второй и третий колодцы, мы закрасим зеленым цветом; утверждается, что из зеленой области не добраться до первого колодца. Вот, собственно, и все. Осталось только посмотреть, где стоит третий дом — в красной, синей или зеленой областях. Вообще, теорема Жордана является одной из фундаментальных теорем топологии и применяется в решении многих важных задач.

В интернете есть игрушка, посвященная задаче о трех домах и трех колодцах. Но программисты были не очень аккуратны: если достаточно быстро двигать мышкой, программа не замечает, что пути от домов к колодцам пересеклись, и иногда выплывает окошко «Поздравляем! Вы решили задачу». Это, конечно, развлекает математиков».

Проблема близнецов

Пары простых чисел, различающихся на 2 — например, 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31, — называются близнецами. Существует ли самая большая пара близнецов?

ГЕОРГИЙ ШАБАТ, профессор кафедры математики, логики и интеллектуальных систем Института лингвистики РГГУ:

«Математикам, как и представителям других древних наук, обычно труднее, чем людям искусства, радовать своими достижениями кого-то за пределами узкого круга коллег. Как правило, не удается даже объяснить, чем мы занимаемся, чего хотим и от чего приходим в восторг. Общие слова (математика ум в порядок приводит…) не помогают; желательны примеры проблем, которые привлекали и привлекают математиков разных эпох и культур и формулировки которых доступны неспециалистам. Но понимание большинства из них требует многолетней подготовки. «Проблема близнецов» — счастливое исключение. Ее формулировка может быть понята пятиклассником.

Число из ряда 2, 3, 4, 5… называется простым, если оно не делится ни на какое из предшествующих чисел этого ряда. Например, число 37 — простое, а число 91=7×13 — не простое (составное).

Существует ли самое большое простое число? Нет. Отрицательный ответ на этот вопрос, содержащийся в знаменитых «Началах» Евклида, — одна из первых теорем мировой математики. Евклид сопроводил ее, вероятно, первым в истории доказательством от противного. Пусть самое большое простое число существует. Тогда можно перемножить все простые числа и прибавить к произведению 1. Полученное число не может делиться ни на одно из простых — по предположению, составляющих полный конечный список. Но оно больше любого числа из этого списка, и поэтому само является простым. Полученное противоречие доказывает теорему о бесконечности множества простых чисел.

Существует ли самая большая пара «близнецов», то есть простых чисел, различающихся на 2? Ответ неизвестен. Заданный вопрос называется проблемой близнецов; современные математики не знают, как подойти к ее решению. На данный момент наибольшими известными близнецами являются числа3756801695685×2666669 ±1.

Позволяет ли освоение проблемы близнецов лучше понять специфику чистой (не прикладной) математики далекому от математики человеку? Нет — если рассматривать эту проблему изолированно, как одну из откуда-то взявшихся сверхтрудных задач. Да — если думать о ней в достаточно широком социальном и историческом контексте. Прежде всего, для проблемы близнецов характерна фундаментальная и демонстративная бесполезность. Серьезному человеку, который спросит, что даст ее решение, ответить нечего. Тем не менее эта проблема веками привлекает внимание: математики видят в ней красоту и (не найденный пока) путь к сокровенным тайнам арифметики.

Социально значимых нерешенных математических проблем во все времена было много, особенно в теории чисел. Но можно ли объяснить неугасающий интерес к некоторым из этих проблем, таким, как проблема близнецов? На мой взгляд, можно — если понимать математику не как набор разрозненных задач, а как процедуру познания единой системы истин (возможно, одной высшей истины, частными случаями которой окажутся все известные сейчас), распределенную по разным эпохам и цивилизациям. В этой процедуре некоторые вопросы оказываются неизбежными и возникают в самых разных культурах: квадратные уравнения, проблемы соизмерения окружности и ее диаметра и вопросы о натуральных числах, в том числе простых. Изолированные вопросы — например, существования нечетных совершенных чисел — забываются, а выживают те, в которых математики предчувствуют встраивание в общие теории будущего. Выше я попытался параллельно рассказать о решенном вопросе (бесконечность множества простых) и нерешенном (бесконечность множества близнецов). Сходством формулировок аналогия не заканчивается. Так, закон распределения простых был эмпирически обнаружен Лежандром и Гауссом на рубеже XVIII и XIX веков и обоснован в течение XIX века Чебышевым, Адамаром и Валле Пуссеном. Гипотетический закон распределения близнецов предложен в XX веке Литтлвудом; обосновать его пока не удается (проблема близнецов из него немедленно следует). Наконец несколько слов о трудности проблемы и о прогрессе математики. Замечательным достижением античной математики было архимедово приближение отношения длины окружности к ее диаметру как 22 к 7. На современном (школьном) языке это дает два знака числа «пи». Сегодня мы умеем вычислять миллионы знаков «пи» и сравнительно легко доказываем несоизмеримость окружности и ее диаметра (иррациональность числа «пи»). Проблема близнецов рано или поздно будет решена. Когда это произойдет, математики сумеют почувствовать, насколько больше они знают, чем мы сегодня«.

Проблема семи стаканов

Проблема семи стаканов

На столе кверху дном стоят 7 стаканов. Разрешается одновременно перевернуть любые 2 стакана. Можно ли добиться того, чтобы все стаканы встали на донышки?

СЕРГЕЙ ЛАНДО, декан факультета математики НИУ «Высшая школа экономики»:

«Я узнал про эту задачу в детстве, на одной из школьных олимпиад по математике, и, ничего не зная об инвариантах, пытался решить ее практически, без особого успеха переворачивая стаканы. Многочисленные попытки поставить стаканы правильно убеждают, что сделать это невозможно. Но можно ли это доказать? Прямой способ доказательства — рассмотреть все возможные положения семерки стаканов. Каждый стакан может находиться в одном из двух положений — стоять на дне или вверх дном. Поэтому 7 стаканов могут находиться в одном из 2×2×2×2×2×2×2=128 положений. Нарисуем на плоскости 128 точек, отвечающих этим положениям, и соединим две такие точки отрезком — в случае, если переворачиванием пары стаканов можно перейти из одного положения в другое. Затем надо убедиться, что нет пути из точки, отвечающей положению «все стаканы вверх дном», в точку «все стаканы стоят на донышках». При правильной организации эта процедура не столь уж трудоемка, несмотря даже на то, что из каждой точки выходит 21 отрезок (количество различных способов выбрать два стакана из семи равно 21).

Однако уже в случае, скажем, 99 стаканов подобная процедура в принципе неприменима — количество возможных расположений стаканов превышает 1029, — и хотелось бы иметь более эффективный способ доказательства невозможности. В то же время ясно, что в некоторых ситуациях придумать необходимый способ переворачивания очень просто. Если стаканов 2, 4, 6 или вообще любое четное количество, достаточно переворачивать пару стоящих вверх дном стаканов, пока все они не окажутся стоящими правильно. Наша задача — понять, чем случай нечетного числа стаканов отличается от случая четного.

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

Подобно биологам, математики хотели бы уметь классифицировать объекты, с которыми им приходится работать. В идеале каждый встреченный математический объект должен быть уложен в предназначенную ему клетку. Инварианты — незаменимый инструмент в такой классификации. Их конструирование приносит эстетическое наслаждение, требует глубоких знаний и изобретательности. Но многие ключевые классификационные задачи далеки от своего разрешения, и необходимые для этого инварианты до сих пор не построены».

Проблема кенигсбергских мостов

Проблема кенигсбергских мостов

Город Кенигсберг (ныне Калининград) расположен на берегах реки Прегель и двух островах. В XVIII веке различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Популярный в течение многих лет вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту? Или хотя бы прогуляться, не возвращаясь?

АЛЕКСЕЙ САМОХИН, завкафедрой высшей математики при МГТУ имени Н.Э. Баумана:

«В 1736 году задача о семи мостах заинтересовала гениального математика Леонарда Эйлера. В результате появилось следующее доказательство. Нанесем на карту схематические маршруты прогулок по мостам. На упрощенной схеме части города (называемой графом) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). Четыре части города обозначены буквами А, В, С и D. Эйлер показал, что с какой бы вершины мы ни начали обход, мы не сможем обойти весь граф и вернуться обратно, не проходя никакого ребра дважды. Ведь если бы такой цикл существовал, то в каждой вершине графа было бы столько же входящих в нее ребер, сколько и выходящих из нее, т.е. в каждой вершине графа было бы четное число ребер. Эйлер в своей работе доказал общее утверждение для связных графов (связность означает, что из любой вершины можно по ребрам перейти в любую другую). Во-первых, на графе можно проложить замкнутый путь, содержащий все ребра графа, причем каждое ребро в точности по одному разу, тогда и только тогда, когда степени всех вершин четны. Во-вторых, можно проложить путь между двумя различными вершинами, содержащий все ребра графа, причем каждое ребро в точности по одному разу, тогда и только тогда, когда это единственные нечетные вершины графа.

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

Исследования Эйлера в теории графов оказались стартовой точкой для создания топологии. Эта отрасль геометрии занимается только порядком расположения частей фигуры друг относительно друга, отвлекаясь от их размеров. Методы топологии применяются в общей теории относительности, анализе и проектировании ДНК… список приложений и здесь необъятен. Интересна несоразмерность исходной задачи и дальних последствий ее решения».

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: