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

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

[Дьюдени правильно показывает, что не более четырех областей можно нарисовать таким образом, чтобы каждая из них имела общий участок границы со всеми другими областями, но ему не удается доказать, что четырех красок будет достаточно для всех карт. Верно, что если любые четыре области на карте рассматривать изолированно, то для любой пятой области не потребуется пятой краски. Но ведь нужно доказать, что на любой карте с большим числом областей эти различные множества из пяти областей не вступят в конфликт друг с другом так, что потребуется пять красок[42].

Возникающую здесь трудность лучше всего можно заметить, если начать и в самом деле строить сложную карту, используя метод, предложенный Дьюдени. Если каждая новая область рисуется таким образом, чтобы она прилегала к трем другим областям, то соответствующая краска выбирается автоматически, и карту из четырех красок можно продолжить до бесконечности. Но если добавляются многие другие области, прилегающие только к одной, двум или вообще ни к одной из предыдущих областей, то выбор красок для этих областей становится произвольным. По мере того как карта увеличивается в размерах и становится все более запутанной, ее создатель неожиданно обнаруживает, что ему требуется пятая краска. Однако, вернувшись назад и изменив цвета предыдущих областей, можно, по-видимому, всегда исправить ошибку и обойтись четырьмя красками. Но в самом ли деле это возможно всегда? Вот что осталось недоказанным. Относительно дискуссии по этой проблеме и ссылок на недавние работы см. гл. 43, посвященную проблеме четырех красок, в моей книге «Математические головоломки и развлечения» (М., изд-во «Мир», 1971). — М. Г.]

432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная, голубая и желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их между собой. Но он не может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике две краски («не хватает одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый, голубой или фиолетовый. Различные оттенки, вроде голубовато-зеленого или желто-зеленого, не допускаются.

433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятой степени равно 1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что у нас только три картины. Тогда одну из них можно выбрать тремя способами, две — тоже тремя способами и три — одним, что в сумме дает 7 способов. Но 7 как раз и равняется 2³ - 1[43].

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! × 2³ = 40 320 способами. Помните, что два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для Ш и У. Отсюда и появляется 2³.

2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединены скобками, а «свободны». Это даст нам 8! × 2² вариантов, но мы должны исключить отсюда результат пункта 1, чтобы не сосчитать некоторые перестановки дважды. Получаем 120 960.

3. Поступим аналогичным образом с двумя «свободными» Ш. Получим 120 960.

4. Поступим так же с двумя «свободными» Ан. Получим 120 960.