З, не окружив либо Ж, либо К. Пусть Г прилегает к К и З; тогда Г нельзя соединить с Ж, не окружив либо Ж, либо З.
Рассмотрим теперь второй вариант, когда КЖЗ лежат на прямой (случай 17). Если Г лежит внутри, то она окружена. Поместим Г снаружи и соединим, как показано, с К и З; тогда Г нельзя соединить с Ж, не окружив при этом либо К, либо З. Пусть Г прилегает к К и Ж; тогда Г нельзя соединить с З, не окружив К или Ж. Пусть Г прилегает к Ж и З; тогда Г нельзя соединить с К, не окружив Ж или З.
Таким образом, мы разобрали все возможные случаи и нашли, что если три страны прилегают друг к другу, то четвертая страна не может прилегать ко всем трем так, чтобы при этом ни одна из стран не оказалась окруженной.
Случай 10 — это случай 8 до преобразования, а случай 11 — то же самое, что и случай 9. Можно заметить, что до К нельзя добраться снаружи. Следовательно, нельзя нарисовать четыре страны таким образом, чтобы пятая страна прилегала к каждой из них; поэтому пятая страна может иметь тот же цвет, что и К. А если нельзя нарисовать пять прилегающих друг к другу стран, то это и подавно невозможно сделать с большим числом стран.
Теперь ясно, что при каждом очередном добавлении новой страны нее страны, нарисованные ранее, должны прилегать друг к другу, чтобы предотвратить повторное использование какой-нибудь краски. При этом условии мы можем нарисовать страны, однако одна из них окажется окруженной. Далее, мы можем нарисовать пятую страну прилегающей только к одной стране (как в случае 12), к двум (как в случае 13) или к трем странам (как в случае 14). В одном случае новой страной может быть Ж, Г или К, во втором — Г или К и в третьем случае — только К. Возьмем последний случай 14 и «предпочтем», или повторим, К. Но при этом мы вынуждены окружить З. Рисуя шестую страну, самое лучшее, что мы можем сделать (пытаясь прийти в противоречие с теоремой), это «предпочесть» З (как в случае 15), а в результате оказывается окруженной К. И так далее до бесконечности. Мы вынуждены окружать какую-нибудь краску на каждом шаге и тем самым делать ее пригодной к употреблению на следующем шаге. Но если вы не можете построить карту, для которой потребовалось бы пять красок, то такой карты и не существует. Следовательно, необходимое число красок никогда не превысит четырех, и теорема доказана.
[Дьюдени правильно показывает, что не более четырех областей можно нарисовать таким образом, чтобы каждая из них имела общий участок границы со всеми другими областями, но ему не удается доказать, что четырех красок будет достаточно для всех карт. Верно, что если любые четыре области на карте рассматривать изолированно, то для любой пятой области не потребуется пятой краски. Но ведь нужно доказать, что на любой карте с большим числом областей эти различные множества из пяти областей не вступят в конфликт друг с другом так, что потребуется пять красок[42].
Возникающую здесь трудность лучше всего можно заметить, если начать и в самом деле строить сложную карту, используя метод, предложенный Дьюдени. Если каждая новая область рисуется таким образом, чтобы она прилегала к трем другим областям, то соответствующая краска выбирается автоматически, и карту из четырех красок можно продолжить до бесконечности. Но если добавляются многие другие области, прилегающие только к одной, двум или вообще ни к одной из предыдущих областей, то выбор красок для этих областей становится произвольным. По мере того как карта увеличивается в размерах и становится все более запутанной, ее создатель неожиданно обнаруживает, что ему требуется пятая краска. Однако, вернувшись назад и изменив цвета предыдущих областей, можно, по-видимому, всегда исправить ошибку и обойтись четырьмя красками. Но в самом ли деле это возможно всегда? Вот что осталось недоказанным. Относительно дискуссии по этой проблеме и ссылок на недавние работы см. гл. 43, посвященную проблеме четырех красок, в моей книге «Математические головоломки и развлечения» (М., изд-во «Мир», 1971). — М. Г.]
432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная, голубая и желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их между собой. Но он не может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике две краски («не хватает одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый, голубой или фиолетовый. Различные оттенки, вроде голубовато-зеленого или желто-зеленого, не допускаются.
433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятой степени равно 1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что у нас только три картины. Тогда одну из них можно выбрать тремя способами, две — тоже тремя способами и три — одним, что в сумме дает 7 способов. Но 7 как раз и равняется 23 - 1[43].
434. Всего имеется 39 147 416 разных способов. Прибавьте 3 к числу членов (что даст 618) и вычтите 1 из числа партий (что даст 3). Тогда ответом будет число способов, которыми можно выбрать 3 предмета из 618, то есть
Общее решение таково. Пусть p — число партий, а m — число членов парламента. Число способов равно числу сочетаний из m + p - 1 объектов по p - 1.
435. Если нет никаких ограничений, то 10 человек могут разместиться на прямой 10! = 3628800 способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек одной национальности, заключенных в скобки, как единое целое.
1. Тогда (Ан, Аи) (Ш, Ш) (У, У) Ф Ит Ис Ам можно переставить 7! × 23 = 40320 способами. Помните, что два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для Ш и У. Отсюда и появляется 23.
2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединены скобками, а «свободны». Это даст нам 8! × 22 вариантов, но мы должны исключить отсюда результат пункта 1, чтобы не сосчитать некоторые перестановки дважды. Получаем 120 960.
3. Поступим аналогичным образом с двумя «свободными» Ш. Получим 120 960.
4. Поступим так же с двумя «свободными» Ан. Получим 120 960.
5. Но мы можем рассмотреть (Ан, Ан) Ш Ш У У Ф Ит Ис Ам, где и Ш, и У «свободны». Это даст нам 9! × 2 случаев, из которых мы должны вычесть результаты пунктов 1, 2 и 3 по очевидным теперь причинам. Получим 443 520.
6. Когда в скобки заключены только Ш, вычтем результаты пунктов 1, 2 и 4. Получим 443 520.
7. Когда в скобках оставлены только У, вычтем результаты пунктов 1, 3 и 4. Получим 443 520.
Сложим результаты семи пунктов и получим при этом 1 733 760. Теперь из самого первого результата вычтем полученное число, что даст нам верный ответ, равный 1 895 040 способам.
436. Головоломку можно решить за 9 переправ следующим образом:
1) мистер и миссис Вебстер переправляются вместе;
2) миссис Вебстер возвращается;
3) переправляются мать и невестка;
4) возвращается мистер Вебстер;
5) переправляются тесть и сын;
6) возвращается невестка;
7) переправляются мистер Вебстер с невесткой;
8) возвращается мистер Вебстер;
9) мистер и миссис Вебстер переправляются вместе.
437. Обозначим трех миссионеров через М м м, а трех каннибалов через К к к; прописными буквами обозначены миссионер и каннибал, умеющие грести. Тогда переправляются К к; К возвращается на лодке; переправляются К к; К возвращается; переправляются М м; возвращаются М к; переправляются М К; возвращаются М к; переправляются М м; возвращается К; переправляются К к; К возвращается; переправляются К к; при этом все переправляются через реку, не нарушая заданных условий.
[Задачи о переправах через реку этого и предыдущего типа решаются с помощью простого метода из теории графов. См. гл. 35 книги М. Гарднера «Математические досуги» (М., изд-во «Мир», 1972). — М. Г.]
438. Двое детей гребут к другому берегу. Один из них вылезает, а другой возвращается назад. Один солдат переправляется, вылезает, а мальчик возвращается назад. Таким образом, чтобы переправить на другой берег одного взрослого, лодка должна 4 раза проплыть от берега до берега. Поэтому ей пришлось сделать 4 × 358 = 1432 рейса, чтобы переправить офицера и 357 солдат, причем лодка в конце концов снова оказалась у детей.
439. Можно составить следующую таблицу:
440. Из таблицы можно сразу определить, что Англия победила Ирландию и сыграла вничью с Уэльсом. Поскольку А сыграла в этих матчах с общим счетом 2 : 0, то она должна была победить со счетом 2 : 0, а вничью сыграть со счетом 0 : 0. Таким образом, нам все известно про А и остается только определить результаты трех матчей: У с И, Ш с И и Ш с У. Шотландия пропустила только 1 гол от У или И. И забила только 1 гол в ворота У или Ш. Допустим, что в ворота Ш. Тогда У не забил ни одного гола в ворота Ш. Но У всего забил 3 гола; следовательно, все они были забиты в ворота И. Получается, что в ворота И было забито 6 голов: 2 — А, 3 — У (если принять, что И забила гол в ворота Ш) и оставшийся гол — Ш. Но поскольку мы приняли, что И забила 1 гол в ворота Ш, матч между этими командами должен был закончиться вничью. Однако из таблицы видно, что в этом матче выиграла Ш и, следовательно, И не могла забить гол в ворота Ш. Таким образом, гол в ворота Ш забил У. А поскольку У всего забил 3 гола, то остальные 2 были забиты в ворота И, которая свой единственный гол забила в ворота У. Окончательно мы получаем, что Ш выиграла у У со счетом 2 : 1, у И со счетом 2 : 0, а У выиграл у И со счетом 2 : 1.