Математические головоломки и развлечения - [132]

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

1. Стифен Барр сообщил мне в письме задачу о художнике, который хочет закончить большую абстрактную картину, изображенную на рис. 223.

Рис. 223Сколько красок должен взять художник, чтобы раскрасить эту абстрактную картину?

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

2. Известный математике Лео Мозер предложил следующую задачу: как начертить на плоскости двухцветную карту, обладающую таким свойством, что, как бы вы ни накладывали на нее равносторонний треугольник со стороной 1, все три его вершины не должны лежать на точках одного цвета?

* * *

Утверждение о том, что на плоскости нельзя начертить пять областей так, чтобы любые из них имели общую границу, было высказано в 1840 году Мёбиусом на одной из его лекций. Мёбиус придал ему форму притчи о восточном правителе, завещавшем свое царство пяти сыновьям при условии, если те сумеют так поделить наследство, чтобы владения каждого из сыновей граничили с владениями всех остальных. Эта задача эквивалентна следующей задаче из теории графов: можно ли так разместить на плоскости пять точек, чтобы они соединялись не пересекающимися друг с другом отрезками прямых? Доказательство того, что этого сделать нельзя, нетрудно, и его можно найти в любой книге по элементарной теории графов.[67]

Неточность выражений, употребленных мной при обсуждении проблемы четырех красок, как утверждения, неразрешимого в смысле Гёделя, послужила причиной следующего письма.

Уважаемая редакция!

Статья Мартина Гарднера о проблеме четырех красок доставила мне много удовольствия. Действительно, невозможно доказать, что доказать эту теорему невозможно. В самом деле, если утверждение теоремы (речь идет о теореме, утверждающей, что четырех красок достаточно для раскрашивания любой карты) ложно, то это, вне всяких сомнений, можно наглядно продемонстрировать, предъявив карту, которую нельзя раскрасить в четыре краски. Следовательно, если теорема недоказуема, то она должна быть верна. Это и означает, что мы не можем доказать, что доказать ее невозможно, ибо такое доказательство было бы эквивалентно доказательству теоремы и мы пришли бы к противоречию.

Аналогичное замечание применимо к любой теореме, ложность которой можно было бы продемонстрировать с помощью контрпримера, в частности к великой теореме Ферма.

Такие теоремы могут быть недоказуемыми, но лишь в том случае, если они истинны. Поэтому мы никогда не можем знать, что они недоказуемы, и математики должны вновь и вновь предпринимать попытки доказать их. Ситуация складывается просто ужасная! Хорошим выходом из нее могло бы послужить обращение к физике, но «гёделевщина» может вторгнуться и в эту область…

Ситуация станет менее ужасной, если учесть, что теорема, неразрешимая в смысле Гёделя в рамках данной дедуктивной системы, всегда может быть разрешена средствами математики в расширенной системе. Если когда-нибудь будет доказано, что проблема четырех красок неразрешима в смысле Гёделя в рамках дедуктивной системы, опирающейся на определенные постулаты топологии и теории множеств, то она автоматически станет «истинной» (как объяснил нам Сиама), но «истинной» в метаматематическом смысле, то есть разрешимой в некоторой более широкой дедуктивной системе, может быть, в системе, в которую утверждение о возможности раскраски любой карты четырьмя красками само входит в качестве нового постулата.

Ответы

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

2. Раскрасить плоскость в два цвета так, чтобы вершины наложенного на нее равностороннего треугольника со стороной в 1 при любой его ориентации не попадали на три точки одного цвета, проще всего так: нужно разделить плоскость на параллельные полосы, каждая шириной в

единиц, а затем попеременно раскрасить их в черный и белый цвета так, как показано на рис. 224.

Рис. 224Решение задачи о треугольнике и двуцветной карте.

Чтобы «полосатая» плоскость давала решение задачи, необходимо ввести понятие открытого и замкнутого множества. Континуум вещественных чисел, например чисел, заключенных между 0 и 1, называется замкнутым интервалом, если 0 и 1 принадлежат ему, и открытым интервалом, если 0 и 1 не принадлежат ему. Если интервал включает один из своих концов (0 или 1) и не включает другого, то говорят, что он замкнут с одного и открыт с другого конца.