Пятьсот двадцать головоломок

Дьюдени Генри Эрнест

[Милли улучшил решение, найдя 76-километровый путь, состоящий из 16 отрезков и не захватывающий только одингород. По-видимому, это наилучшее возможное решение. Читатель может попытаться его найти. — М. Г.]

417. На рисунке, где для большей ясности опущены неиспользованные дороги, показаны маршруты всех 5 автомобилей. Все маршруты не имеют общих участков и не пересекаются. Хотя точного правила для решения головоломок такого рода указать нельзя, тем не менее, внимательно подумав, мы обычно можем справиться со встретившимися здесь трудностями. Например, уже было показано, что если соединить Aс Aпо вертикали, то C, Dи Eокажутся отрезанными друг от друга. Вскоре выясняется, что путь из Aдолжен обойти слева верхнее D, а затем пройти справа от C.

Таким образом, становится очевидным путь из Dв Dи из Bв B. Остальное закончить уже легко.

418. При любом способе первой буквой должна быть M, а поскольку у нас всего четыре буквы M, то мы можем начинать только из четырех точек. Можно показать, что при фиксированном начальном Mсуществует 20 различных способов; следовательно, всего имеется 80 способов.

419. Эту головоломку можно решить с помощью поразительно малого числа росчерков, а именно 14, начиная из Aи заканчивая в Z. На рисунке, помещенном слева, сознательно оставлены пробелы, чтобы сделать яснее путь карандаша.

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

41

См. решение задачи 403. — Прим. перев.

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

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