Генри Дьюдени - Пятьсот двадцать головоломок

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

Случай 10 — это случай 8 до преобразования, а случай 11 — то же самое, что и случай 9 . Можно заметить, что до К нельзя добраться снаружи. Следовательно, нельзя нарисовать четыре страны таким образом, чтобы пятая страна прилегала к каждой из них; поэтому пятая страна может иметь тот же цвет, что и К . А если нельзя нарисовать пять прилегающих друг к другу стран, то это и подавно невозможно сделать с большим числом стран.

Теперь ясно, что при каждом очередном добавлении новой страны нее страны, нарисованные ранее, должны прилегать друг к другу, чтобы предотвратить повторное использование какой-нибудь краски. При этом условии мы можем нарисовать страны, однако одна из них окажется окруженной. Далее, мы можем нарисовать пятую страну прилегающей только к одной стране (как в случае 12 ), к двум (как в случае 13 ) или к трем странам (как в случае 14 ). В одном случае новой страной может быть Ж , Г или К , во втором — Г или К и в третьем случае — только К . Возьмем последний случай 14 и «предпочтем», или повторим, К . Но при этом мы вынуждены окружить З . Рисуя шестую страну, самое лучшее, что мы можем сделать (пытаясь прийти в противоречие с теоремой), это «предпочесть» З (как в случае 15 ), а в результате оказывается окруженной К . И так далее до бесконечности. Мы вынуждены окружать какую-нибудь краску на каждом шаге и тем самым делать ее пригодной к употреблению на следующем шаге. Но если вы не можете построить карту, для которой потребовалось бы пять красок, то такой карты и не существует. Следовательно, необходимое число красок никогда не превысит четырех, и теорема доказана.

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

Возникающую здесь трудность лучше всего можно заметить, если начать и в самом деле строить сложную карту, используя метод, предложенный Дьюдени. Если каждая новая область рисуется таким образом, чтобы она прилегала к трем другим областям, то соответствующая краска выбирается автоматически, и карту из четырех красок можно продолжить до бесконечности. Но если добавляются многие другие области, прилегающие только к одной, двум или вообще ни к одной из предыдущих областей, то выбор красок для этих областей становится произвольным. По мере того как карта увеличивается в размерах и становится все более запутанной, ее создатель неожиданно обнаруживает, что ему требуется пятая краска. Однако, вернувшись назад и изменив цвета предыдущих областей, можно, по-видимому, всегда исправить ошибку и обойтись четырьмя красками. Но в самом ли деле это возможно всегда? Вот что осталось недоказанным. Относительно дискуссии по этой проблеме и ссылок на недавние работы см. гл. 43, посвященную проблеме четырех красок, в моей книге «Математические головоломки и развлечения» (М., изд-во «Мир», 1971). — М. Г. ]

432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная, голубая и желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их между собой. Но он не может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике две краски («не хватает одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый, голубой или фиолетовый. Различные оттенки, вроде голубовато-зеленого или желто-зеленого, не допускаются.

433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятой степени равно 1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что у нас только три картины. Тогда одну из них можно выбрать тремя способами, две — тоже тремя способами и три — одним, что в сумме дает 7 способов. Но 7 как раз и равняется 2 3- 1 [43] Из n предметов m можно выбрать C n m = способами. Общая сумма способов равна 1 + C n 1 + C n 2 + ... + C n n = (1 + 1) n = 2 n . Сюда вошел и «способ», при котором мы вообще ничего не выбираем (не дарим ни одной картины). Исключив его, мы и получим 2 n - 1. — Прим. перев. .