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

423. Из рисунка видно, что путь узника полностью удовлетворяет заданным условиям, пока узник не попадает в b. Дойдя до этой точки, узнику следовало бы поставить одну ногу в точку c, находящуюся в соседней камере, и сказать: «Поскольку одна нога находится в c, то я, несомненно, вошел в эту камеру и все же, убрав ногу назад, я не вошел тем самым в b во второй раз по той простой причине, что ее и не покидал с тех пор, как вошел туда в первый раз!»

424. На рисунке показан изящный способ посадки деревьев в 9 рядов по 4 дерева в каждом.

425. Расположите 16 монет в виде квадрата 4 × 4. Затем положите по одной монете сверху на первую монету первой строки, на третью монету второй, на четвертую — третьей и на вторую — четвертой строки.

426. На рисунке показано, как следует пересадить 6 деревьев, чтобы получилось 20 рядов по 4 дерева в каждом.

427. На рисунке показано, как следует расположить колышки. Три колышка из дырок, отмеченных крестиками, надо поместить в левый верхний угол. После этого 10 колышков образуют 5 рядов по 4 колышка в каждом. Если вы отразите диаграмму в зеркале, то получите единственное решение, отличное от данного.

428. Решение показано на рисунке. Десять фишек образуют 5 прямых по 4 фишки на каждой.

429. На рисунке видно, что корабли образуют 5 прямых по 4 корабля на каждой, а белые призрачные корабли указывают позиции, с которых 4 из них были перемещены.

430. На рисунке представлено симметричное решение, при котором 21 звезда образует 11 прямых по 5 звезд на каждой прямой.

431. Очевидно, что для двух и большего числа прилегающих стран необходимы по крайней мере две краски (случай 1). Если три страны попарно прилегают друг к другу, то необходимы три краски (случай 2). Для четырех стран требуются три краски, если четвертая (Ж) страна прилегает к двум другим, уже прилегающим друг к другу (случай 3). (Поскольку возможен вариант, когда, как в случае 4, краска 3 прилегает к двум не прилегающим друг к другу странам, и в силу этого можно обойтись двумя красками.) Четыре же краски понадобятся и в случае, когда четвертая страна прилегает к каждой из трех прилегающих друг к другу стран (случай 5).

Для пяти прилегающих стран потребуются 3 краски, если одна страна прилегает к двум прилегающим друг к другу странам (случай 6). Четыре краски потребуются, если пятая страна прилегает к каждой из трех прилегающих друг к другу стран (случай 7). Однако 5 красок потребовались бы в случае, если бы пятая страна прилегала к четырем прилегающим друг к другу странам. Если такая карта возможна, то теорема не верна.

Рассмотрим сначала четыре страны, прилегающие друг к другу. Мы произведем небольшое преобразование, приняв, что любые две прилегающие друг к другу страны связаны между собой мостом. Мост может иметь любую длину, а страны можно свести просто к точкам, не влияя на условия[41]. В случаях 8 и 9 я изобразил четыре страны (точки), соединенные между собой мостами (линиями). Относительное расположение этих точек совершенно несущественно, и выясняется, что в каждом возможном случае к одной из стран (точек) нельзя подобраться снаружи.

Это легко доказать. Если 3 точки связаны между собой прямыми, то эти точки должны либо образовывать треугольник, либо лежать на одной прямой. Предположим сначала, что они образуют треугольник ЖКЗ, как в случае 16. Тогда четвертая страна (Г) должна лежать либо внутри треугольника, либо вне его. Если она лежит внутри, то очевидно, что она окружена. Поместим ее снаружи и соединим с Ж и З, как показано на рисунке; тогда Г нельзя соединить с К, не окружив при этом Ж или З. Пусть Г прилегает к Ж или К; тогда Г нельзя соединить с З, не окружив либо Ж, либо К. Пусть Г прилегает к К и З; тогда Г нельзя соединить с Ж, не окружив либо Ж, либо З.

Рассмотрим теперь второй вариант, когда КЖЗ лежат на прямой (случай 17). Если Г лежит внутри, то она окружена. Поместим Г снаружи и соединим, как показано, с К и З; тогда Г нельзя соединить с Ж, не окружив при этом либо К, либо З. Пусть Г прилегает к К и Ж; тогда Г нельзя соединить с З, не окружив К или Ж. Пусть Г прилегает к Ж и З; тогда Г нельзя соединить с К, не окружив Ж или З.

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

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

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

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

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

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