Ознакомительная версия. Доступно 22 страниц из 110
она соперничала с Великой теоремой Ферма за звание самой знаменитой головоломки в истории математики. Наконец, в 1976 году мир узнал, что загадка разгадана. Однако когда стало известно, как именно это было сделано, праздничное настроение сменилось огорчением, скептицизмом и откровенным недоверием. Оказалось, что проблема, считавшаяся задачей чистой математики, обернулась философским вопросом, точнее, даже двумя: во-первых о том как в научном сообществе положено подтверждать свои претензии на математические знания, а во-вторых о том, может ли машинный интеллект помочь нам усвоить априорные истины.
При всей своей математической и философской занятности проблема четырех красок не имела очевидного практического применения, по крайней мере, для картографов, которые не проявляют склонности минимизировать количество используемых цветов. Однако, чтобы подойти к задаче, полезно взглянуть на атлас. Обратимся к карте Европы – к той ее части, где расположены Бельгия, Франция, Германия и Люксембург. Каждая из этих стран граничит с остальными тремя, поэтому очевидно, что для того, чтобы они не сливались, потребуется не меньше четырех красок. Вероятно, читатель сочтет, что четыре цвета нужны только тогда, когда на карте есть подобный квартет соседствующих друг с другом областей. Если вы так думаете, обратитесь к карте США и посмотрите на штат Невада, окаймленный пятью другими штатами (Калифорния, Орегон, Айдахо, Юта и Аризона). Ни одна комбинация штатов не соседствует друг с другом так, как Бельгия, Франция, Германия и Люксембург. Однако это скопление в целом невозможно раскрасить меньше чем четырьмя цветами так, чтобы никакая пара штатов не сливалась, в чем легко убедиться самостоятельно. С другой стороны, Вайоминг и шесть окружающих его штатов вполне можно раскрасить всего тремя цветами – какой удар для интуиции!
Некоторым картам нужно четыре краски, и этого достаточно. Проблема четырех красок гласит, что невозможно составить карту, которой было бы нужно больше четырех цветов. Что значит «доказать» такую гипотезу? Варианта два. Предположим, как считают некоторые математики, что она ложна. Тогда достаточно нарисовать всего одну карту, для раскрашивания которой нужно пять и более цветов, и вопрос закрыт. (В апреле 1975 года Мартин Гарднер опубликовал в журнале Scientific American сложнейшую карту из 110 регионов, которую, по его словам, невозможно было раскрасить меньше чем пятью цветами. Сотни читателей прислали в редакцию копии карты, старательно раскрашенные всего в четыре цвета: должно быть, они не сообразили, что Гарднер решил порадовать себя маленькой первоапрельской шуткой.) А чтобы доказать, что гипотеза четырех цветов верна, придется показать, что любая мыслимая карта – а их бесконечно много – может быть раскрашена всего четырьмя красками, какими бы многочисленными, сложнозакрученными и перепутанными ни были обозначенные на ней области.
Поэтому простота проблемы четырех красок обманчива. А чтобы осознать, насколько обманчива, стоит взглянуть на долгую историю попыток ее доказать или опровергнуть – настоящую комедию ошибок. Судя по всему, Фрэнсис Гатри, который в 1852 году заподозрил, что хватит и четырех красок, считал, что доказал свою гипотезу. Впоследствии Гатри стал профессором математики в Южной Африке, однако за всю свою жизнь не опубликовал ни одной работы, касающейся проблемы четырех красок: очевидно, его больше интересовала ботаника (в его честь назван вид вереска). Однако он обсуждал проблему со своим младшим братом Фредериком, который привлек к ней внимание своего профессора математики Огастеса де Моргана. Де Морган был очень способным математиком и важной фигурой в истории логики. Проблема четырех красок заинтересовала его, и он очень увлекся мыслью, что если карта содержит четыре взаимно граничащие области, одна из них должна быть полностью окружена остальными тремя (если вернуться к вышеприведенному примеру, то Люксембург полностью окружен Бельгией, Францией и Германией). Де Морган полагал – ошибочно, – что эта «скрытая аксиома» необходима для доказательства гипотезы, над которым он ломал голову до самой своей смерти – он скончался в 1871 году.
Именно де Морган впервые упомянул о гипотезе четырех красок в печати, причем не где-нибудь, а в анонимной философской заметке, которую он послал в 1860 году в популярный литературный журнал Athenaeum. Слухи о заметке пересекли Атлантику и дошли до США, где под колдовское обаяние гипотезы подпал философ Чарльз Пирс. Пирс заявил, что «со стороны логики и математики непростительное упущение, что такое простое утверждение до сих пор не доказано», и в конце 1860-х годов предложил собственное гипотетическое доказательство гарвардскому математическому обществу. Никаких сведений о нем не сохранилось. Однако впоследствии Пирс был вынужден признать верность доказательства, которое предоставил другой ученый, и поспособствовать его публикации в Nation в Рождество 1879 года. Тем самым Пирс невольно подтвердил истинность доказательства, которому предстояло стать самым знаменитым примером пагубного заблуждения в истории математики.
Здесь, пожалуй, уместно сказать несколько слов о том, как математики вообще относятся к доказательствам утверждений, особенно таких, которые, подобно проблеме четырех красок, охватывают бесконечное множество случаев. Один из методов доказательства называется математической индукцией. Иногда его сравнивают с тем, как падает бесконечный ряд косточек домино. Главное в методе математической индукции – показать, что если такое-то и такое-то утверждение верно для числа n, то тогда оно верно и для n+1. Аналогия с домино означает, что каждая падающая косточка сбивает следующую в очереди, и в конце концов упадут все. Чтобы применить математическую индукцию к проблеме четырех красок, нужно показать, что если каждая карта, на которой обозначено n областей, может быть раскрашена четырьмя красками, это возможно и для карты, на которой n+1 областей. Как выяснилось, это чудовищно трудно. Когда добавляешь на данную карту «эн-плюс-первую» область, иногда приходится перекрасить некоторые или все n остальных областей, чтобы новая область вписалась в четырехцветную схему. Общее правило такой перекраски никому сформулировать не удалось. Так что никакого падения доминошек.
К счастью, есть и другой подход к доказательству утверждения, охватывающего бесконечно много случаев: доказательство от противного. Берешь утверждение, противоположное тому, которое хочешь доказать, и доводишь его до абсурда. В случае проблемы четырех красок это означает, что мы предполагаем, что существуют контрпримеры, то есть карты, для которых нужно пять и более красок, а затем выводим из этого предположения противоречие. Поскольку подобные контрпримеры нарушают принцип четырех красок, их принято в обиходе называть «криминальными». Если криминальные карты существуют, в них может быть любое количество областей, но полезно сосредоточиться на тех, где областей абсолютный минимум. Такие карты называют «минимальными» криминальными картами. (Очевидно, чтобы потребовалось пять цветов, на минимальной криминальной карте должно быть не меньше пяти областей.) Любая карта с меньшим числом областей, чем минимальная криминальная, по определению законопослушна, то есть ее можно раскрасить в четыре цвета.
Мы оказались
Ознакомительная версия. Доступно 22 страниц из 110
