420. Нарисовать змею менее чем 13 линиями невозможно. Поэтому необходимо найти самую длинную из этих линий. На нашем рисунке мы начинаем в A, а кончаем в B или наоборот. Пунктиром обозначены пропущенные линии. Чтобы найти решение, требуется немного подумать. Так, непрерывная линия из D в C длиннее пунктирной, следовательно, мы выбираем первую. Точно так же мы увеличим длину линии, если нарисуем язык вместо рта, но при этом кончик языка, изображенный в виде отрезка прямой, мы обязаны отбросить.
421. Существуют разные варианты решения; один из них показан на рисунке. Однако совершенно необходимо, чтобы вы начинали в A, а кончали в B или наоборот. В любой другой точке сходятся две или четыре (четное число) линии, а в A и B - три (нечетное число). Следовательно, начало и конец пути должны совпадать с A и B.
422. Головоломку решить можно, но при этом необходимо начинать рисунок в точке A, а кончать его в B или наоборот. В противном случае начертить требуемую фигуру одной непрерывной линией нельзя.
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 красок потребовались бы в случае, если бы пятая страна прилегала к четырем прилегающим друг к другу странам. Если такая карта возможна, то теорема не верна.
Рассмотрим сначала четыре страны, прилегающие друг к другу. Мы произведем небольшое преобразование, приняв, что любые две прилегающие друг к другу страны связаны между собой мостом. Мост может иметь любую длину, а страны можно свести просто к точкам, не влияя на условия. В случаях 8 и 9 я изобразил четыре страны (точки), соединенные между собой мостами (линиями). Относительное расположение этих точек совершенно несущественно, и выясняется, что в каждом возможном случае к одной из стран (точек) нельзя подобраться снаружи.
Это легко доказать. Если 3 точки связаны между собой прямыми, то эти точки должны либо образовывать треугольник, либо лежать на одной прямой. Предположим сначала, что они образуют треугольник ЖКЗ, как в случае 16. Тогда четвертая страна (Г) должна лежать либо внутри треугольника, либо вне его. Если она лежит внутри, то очевидно, что она окружена. Поместим ее снаружи и соединим с Ж и З, как показано на рисунке; тогда Г нельзя соединить с К, не окружив при этом Ж или З. Пусть Г прилегает к Ж или К; тогда Г нельзя соединить с З, не окружив либо Ж, либо К. Пусть Г прилегает к К и З; тогда Г нельзя соединить с Ж, не окружив либо Ж, либо З.
Рассмотрим теперь второй вариант, когда КЖЗ лежат на прямой (случай 17). Если Г лежит внутри, то она окружена. Поместим Г снаружи и соединим, как показано, с К и З; тогда Г нельзя соединить с Ж, не окружив при этом либо К, либо З. Пусть Г прилегает к К и Ж; тогда Г нельзя соединить с З, не окружив К или Ж. Пусть Г прилегает к Ж и З; тогда Г нельзя соединить с К, не окружив Ж или З.
Таким образом, мы разобрали все возможные случаи и нашли, что если три страны прилегают друг к другу, то четвертая страна не может прилегать ко всем трем так, чтобы при этом ни одна из стран не оказалась окруженной.
Случай 10 - это случай 8 до преобразования, а случай 11 - то же самое, что и случай 9. Можно заметить, что до К нельзя добраться снаружи. Следовательно, нельзя нарисовать четыре страны таким образом, чтобы пятая страна прилегала к каждой из них; поэтому пятая страна может иметь тот же цвет, что и К. А если нельзя нарисовать пять прилегающих друг к другу стран, то это и подавно невозможно сделать с большим числом стран.
Теперь ясно, что при каждом очередном добавлении новой страны нее страны, нарисованные ранее, должны прилегать друг к другу, чтобы предотвратить повторное использование какой-нибудь краски. При этом условии мы можем нарисовать страны, однако одна из них окажется окруженной. Далее, мы можем нарисовать пятую страну прилегающей только к одной стране (как в случае 12), к двум (как в случае 13) или к трем странам (как в случае 14). В одном случае новой страной может быть Ж, Г или К, во втором - Г или К и в третьем случае - только К. Возьмем последний случай 14 и "предпочтем", или повторим, К. Но при этом мы вынуждены окружить З. Рисуя шестую страну, самое лучшее, что мы можем сделать (пытаясь прийти в противоречие с теоремой), это "предпочесть" З (как в случае 15), а в результате оказывается окруженной К. И так далее до бесконечности. Мы вынуждены окружать какую-нибудь краску на каждом шаге и тем самым делать ее пригодной к употреблению на следующем шаге. Но если вы не можете построить карту, для которой потребовалось бы пять красок, то такой карты и не существует. Следовательно, необходимое число красок никогда не превысит четырех, и теорема доказана.