Математические головоломки и развлечения
Шрифт:
Рис. 222 Двух красок достаточно для раскрашивания карты, образованной либо линиями, идущими от одного края листа до другого, либо замкнутыми кривыми.
Проведя еще одну кривую, пересекающую всю карту от одного ее края до другого, мы должны, как и прежде, изменить все цвета по одну сторону от кривой на противоположные. Если вновь проведенная кривая замкнута, то изменить нужно окраску всех областей, попавших внутрь кривой, или, если угодно, всех областей, оказавшихся снаружи. Замкнутые кривые могут иметь и точки самопересечения, но в этом случае перекрашивание областей более сложно.
Заметим, что на всех приведенных здесь двухцветных картах все вершины четны (напомним, что вершиной называется точка, в которой сходятся границы более двух стран), то есть в каждой вершине сходится четное число границ. Можно показать, что любую карту на плоскости можно раскрасить в два цвета тогда и только тогда, когда все ее вершины четны. Это утверждение известно как «теорема о двухцветных картах». Нетрудно видеть, что на торе эта теорема не выполняется. Для этого достаточно скатать в трубку квадратный лист бумаги, расчерченный на девять маленьких квадратов (наподобие игрового поля для крестиков и ноликов), а концы трубки склеить. Все вершины на таком «клетчатом» торе четны, но для его раскрашивания необходимо взять три краски.
Приведем теперь (скорее для развлечения, чем для уяснения существа дела) две задачи на раскрашивание карт. Они несложны, но в каждой имеется какая-нибудь ловушка, которая делает решение не столь легким, как это кажется с первого взгляда.
1. Стифен Барр сообщил мне в письме задачу о художнике, который хочет закончить большую абстрактную картину, изображенную на рис. 223.
Рис. 223 Сколько красок должен взять художник, чтобы раскрасить эту абстрактную картину?
Он решил ограничиться четырьмя красками и каждую из областей окрасить только в один цвет, следя за тем, чтобы области, имеющие общую границу, не были окрашены одинаково. Площадь каждой области равна восьми квадратным футам, за исключением верхней области, имеющей вдвое большую площадь, чем остальные. Проверив запасы красок в тюбиках, художник обнаружил, что красной краски у него осталось ровно столько, сколько требуется, чтобы покрыть 24 квадратных фута, желтой хватит на покрытие такой же площади, зеленой — на 16 квадратных футов и синей — на 8 квадратных футов. Как ему следует поступить для того, чтобы закончить свою картину?
2. Известный математике Лео Мозер предложил следующую задачу: как начертить на плоскости двухцветную карту, обладающую таким свойством, что, как бы вы ни накладывали на нее равносторонний треугольник со стороной 1, все три его вершины не должны лежать на точках одного цвета?
* * *
Утверждение о том, что на плоскости нельзя начертить пять областей так, чтобы любые из них имели общую границу, было высказано в 1840 году Мёбиусом на одной из его лекций. Мёбиус придал ему форму притчи о восточном правителе, завещавшем свое царство пяти сыновьям при условии, если те сумеют так поделить наследство, чтобы владения каждого из сыновей граничили с владениями всех остальных. Эта задача эквивалентна следующей задаче из теории графов: можно ли так разместить на плоскости пять точек, чтобы они соединялись не пересекающимися друг с другом отрезками прямых? Доказательство того, что этого сделать нельзя, нетрудно, и его можно найти в любой книге по элементарной теории графов. [67]
67
Tietze H., Famous Problems of Mathematics. — Graylock Press, 1965, pp. 64–89.
Неточность выражений, употребленных мной при обсуждении проблемы четырех красок, как утверждения, неразрешимого в смысле Гёделя, послужила причиной следующего письма.
Уважаемая редакция!
Статья Мартина Гарднера о проблеме четырех красок доставила мне много удовольствия. Действительно, невозможно доказать, что доказать эту теорему невозможно. В самом деле, если утверждение теоремы (речь идет о теореме, утверждающей, что четырех красок достаточно для раскрашивания любой карты) ложно, то это, вне всяких сомнений, можно наглядно продемонстрировать, предъявив карту, которую нельзя раскрасить в четыре краски. Следовательно, если теорема недоказуема, то она должна быть верна. Это и означает, что мы не можем доказать, что доказать ее невозможно, ибо такое доказательство было бы эквивалентно доказательству теоремы и мы пришли бы к противоречию.
Аналогичное замечание применимо к любой теореме, ложность которой можно было бы продемонстрировать с помощью контрпримера, в частности к великой теореме Ферма.
Такие теоремы могут быть недоказуемыми, но лишь в том случае, если они истинны. Поэтому мы никогда не можем знать, что они недоказуемы, и математики должны вновь и вновь предпринимать попытки доказать их. Ситуация складывается просто ужасная! Хорошим выходом из нее могло бы послужить обращение к физике, но «гёделевщина» может вторгнуться и в эту область…
Ситуация станет менее ужасной, если учесть, что теорема, неразрешимая в смысле Гёделя в рамках данной дедуктивной системы, всегда может быть разрешена средствами математики в расширенной системе. Если когда-нибудь будет доказано, что проблема четырех красок неразрешима в смысле Гёделя в рамках дедуктивной системы, опирающейся на определенные постулаты топологии и теории множеств, то она автоматически станет «истинной» (как объяснил нам Сиама), но «истинной» в метаматематическом смысле, то есть разрешимой в некоторой более широкой дедуктивной системе, может быть, в системе, в которую утверждение о возможности раскраски любой карты четырьмя красками само входит в качестве нового постулата.
Ответы
1. Смешав всю имеющуюся у него синюю краску с третью всего количества красной краски, художник получил столько пурпурной краски, что ее хватило для закрашивания шестнадцати квадратных футов полотна. После того как большая область в верхней части абстрактной картины (рис. 223) и центральная область закрашены в желтый цвет, раскрасить остальные области в красный, зеленый и пурпурный цвета уже нетрудно.
2. Раскрасить плоскость в два цвета так, чтобы вершины наложенного на нее равностороннего треугольника со стороной в 1 при любой его ориентации не попадали на три точки одного цвета, проще всего так: нужно разделить плоскость на параллельные полосы, каждая шириной в
единиц, а затем попеременно раскрасить их в черный и белый цвета так, как показано на рис. 224.
Рис. 224 Решение задачи о треугольнике и двуцветной карте.
Чтобы «полосатая» плоскость давала решение задачи, необходимо ввести понятие открытого и замкнутого множества. Континуум вещественных чисел, например чисел, заключенных между 0 и 1, называется замкнутым интервалом, если 0 и 1 принадлежат ему, и открытым интервалом, если 0 и 1 не принадлежат ему. Если интервал включает один из своих концов (0 или 1) и не включает другого, то говорят, что он замкнут с одного и открыт с другого конца.
Полосы на карте будем считать замкнутыми слева и открытыми справа. Самая левая черная полоса начинается с отметки 0 (внизу) и доходит до отметки
но не включает эту отметку. Следующая (белая) полоса включает отметку
и доходит до отметки
не включая ее, и т. д. Иначе говоря, каждая вертикальная линия на карте принадлежит лишь той полосе, которая расположена справа от нее. Это необходимо для соблюдения условий задачи в тех случаях, когда все три вершины треугольника (рис. 224) должны были бы располагаться на границах между полосами.