Пятьсот двадцать головоломок
Шрифт:
Таким образом, мы разобрали все возможные случаи и нашли, что если три страны прилегают друг к другу, то четвертая страна не может прилегать ко всем трем так, чтобы при этом ни одна из стран не оказалась окруженной.
Случай 10 — это случай 8до преобразования, а случай 11 — то же самое, что и случай 9. Можно заметить, что до Кнельзя добраться снаружи. Следовательно, нельзя нарисовать четыре страны таким образом, чтобы пятая страна прилегала к каждой из них; поэтому пятая страна может иметь тот же цвет, что и К. А если нельзя нарисовать пять прилегающих друг к другу стран, то это и подавно невозможно сделать с большим числом стран.
Теперь ясно, что при каждом очередном добавлении новой страны нее страны,
[Дьюдени правильно показывает, что не более четырех областей можно нарисовать таким образом, чтобы каждая из них имела общий участок границы со всеми другими областями, но ему не удается доказать, что четырех красок будет достаточно для всех карт. Верно, что если любые четыре области на карте рассматривать изолированно, то для любой пятой области не потребуется пятой краски. Но ведь нужно доказать, что на любой карте с большим числом областей эти различные множества из пяти областей не вступят в конфликт друг с другом так, что потребуется пять красок [42] .
42
Можно сказать, что Дьюдени доказал локальную, а не глобальную теорему. — Прим. перев.
Возникающую здесь трудность лучше всего можно заметить, если начать и в самом деле строить сложную карту, используя метод, предложенный Дьюдени. Если каждая новая область рисуется таким образом, чтобы она прилегала к трем другим областям, то соответствующая краска выбирается автоматически, и карту из четырех красок можно продолжить до бесконечности. Но если добавляются многие другие области, прилегающие только к одной, двум или вообще ни к одной из предыдущих областей, то выбор красок для этих областей становится произвольным. По мере того как карта увеличивается в размерах и становится все более запутанной, ее создатель неожиданно обнаруживает, что ему требуется пятая краска. Однако, вернувшись назад и изменив цвета предыдущих областей, можно, по-видимому, всегда исправить ошибку и обойтись четырьмя красками. Но в самом ли деле это возможно всегда? Вот что осталось недоказанным. Относительно дискуссии по этой проблеме и ссылок на недавние работы см. гл. 43, посвященную проблеме четырех красок, в моей книге «Математические головоломки и развлечения» (М., изд-во «Мир», 1971). — М. Г.]
432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная, голубая и желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их между собой. Но он не может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике две краски («не хватает одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый, голубой или фиолетовый. Различные оттенки, вроде голубовато-зеленого или желто-зеленого, не допускаются.
433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятой степени равно 1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что у нас только три картины. Тогда одну из них можно выбрать тремя способами, две — тоже тремя способами
43
Из nпредметов mможно выбрать C n m =
434. Всего имеется 39 147 416 разных способов. Прибавьте 3 к числу членов (что даст 618) и вычтите 1 из числа партий (что даст 3). Тогда ответом будет число способов, которыми можно выбрать 3 предмета из 618, то есть
Общее решение таково. Пусть p — число партий, а m — число членов парламента. Число способов равно числу сочетаний из m+ p– 1 объектов по p– 1.
435. Если нет никаких ограничений, то 10 человек могут разместиться на прямой 10! = 3 628 800 способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек одной национальности, заключенных в скобки, как единое целое.
1. Тогда (Ан, Аи) (Ш, Ш) (У, У) Ф Ит Ис Ам можно переставить 7! x 2 3= 40 320 способами. Помните, что два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для Ш и У. Отсюда и появляется 2 3.
2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединены скобками, а «свободны». Это даст нам 8! x 2 2вариантов, но мы должны исключить отсюда результат пункта 1, чтобы не сосчитать некоторые перестановки дважды. Получаем 120 960.
3. Поступим аналогичным образом с двумя «свободными» Ш. Получим 120 960.
4. Поступим так же с двумя «свободными» Ан. Получим 120 960.
5. Но мы можем рассмотреть (Ан, Ан) Ш Ш У У Ф Ит Ис Ам, где и Ш, и У «свободны». Это даст нам 9! x 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. Обозначим трех миссионеров через М м м, а трех каннибалов через К к к; прописными буквами обозначены миссионер и каннибал, умеющие грести. Тогда переправляются К к; К возвращается на лодке; переправляются К к; К возвращается; переправляются М м; возвращаются М к; переправляются М К; возвращаются М к; переправляются М м; возвращается К; переправляются К к; К возвращается; переправляются К к; при этом все переправляются через реку, не нарушая заданных условий.