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

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] См. решение задачи 403. — Прим. перев. . В случаях 8 и 9 я изобразил четыре страны (точки), соединенные между собой мостами (линиями). Относительное расположение этих точек совершенно несущественно, и выясняется, что в каждом возможном случае к одной из стран (точек) нельзя подобраться снаружи.

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

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

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

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

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