<< Предыдущая

стр. 40
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>





[Дьюдени правильно показывает, что не более четырех областей можно нарисовать таким образом,T чтобы
T T




каждая из них имела общий участок границы со всеми другими областями, но ему не удаетсяT доказать, что T




четырех красок будет достаточно для всех карт. Верно, что если любые четыреT области на карте рассматривать T




изолированно, то для любой пятой области не потребуется пятойT краски. Но ведь нужно доказать, что на любой T




карте с большим числом областей эти различныеT множества из пяти областей не вступят в конфликт друг с T




другом так, что потребуется пятьT красокH42.T PU UTHP
T




Возникающую здесь трудность лучше всего можно заметить, если начать и в самом делеT строить сложную
T T




карту, используя метод, предложенный Дьюдени. Если каждая новая областьT рисуется таким образом, чтобы T




она прилегала к трем другим областям, то соответствующая краскаT выбирается автоматически, и карту из T




четырех красок можно продолжить до бесконечности. Но еслиT добавляются многие другие области, T




прилегающие только к одной, двум или вообще ни к одной изT предыдущих областей, то выбор красок для этих T




областей становится произвольным. По мере того какT карта увеличивается в размерах и становится все более T




запутанной, ее создатель неожиданноT обнаруживает, что ему требуется пятая краска. Однако, вернувшись назад T




и изменив цветаT предыдущих областей, можно, по-видимому, всегда исправить ошибку и обойтись четырьмяT
T




красками. Но в самом ли деле это возможно всегда? Вот что осталось недоказанным. ОтносительноT дискуссии
T T




по этой проблеме и ссылок на недавние работы см. гл. 43, посвященную проблеме четырехT красок, в моей книге T




«Математические головоломки и развлечения» (М., изд-во «Мир», 1971).— М.T Г.T] T T T T




432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная,T голубая и
T T




желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их междуT собой. Но он не T




может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике двеT краски («не хватает T




одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый,T голубой или фиолетовый. T




Различные оттенки, вроде голубовато-зеленого или желто-зеленого, неT допускаются.T T




433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятойT степени равно
T T




1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что уT нас только три картины. Тогда T




одну из них можно выбрать тремя способами, две — тожеT тремя способами и три — одним, что в сумме дает 7 T




способов. Но 7 как раз и равняетсяT 23 - 143.T TP HTPTU UTHP
T TP T T




434. Всего имеется 39 147 416 разных способов. Прибавьте 3 к числу членов (что даст 618) и вычтите 1T из
T T




числа партий (что даст 3). Тогда ответом будет число способов, которыми можно выбрать 3 предмета изT 618, то T




естьT




Общее решение таково. Пусть p — число партий, а m — число членов парламента. Число способов равноT
T T T T T




числу сочетаний из m + p - 1 объектов по p - 1.
T T T T T T T T T T T T




435. Если нет никаких ограничений, то 10 человек могут разместиться на прямой 10! = 3T 628T 800T
T T T T T T




способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек однойT
T




национальности, заключенных в скобки, как единое целое.T
T




1. Тогда (Ан, Аи) (Ш, Ш) (У, У) Ф Ит Ис Ам можно переставить 7! 23 = 40T 320 способами. Помните,T что TP
T T T T TP T T T T T




два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самоеT верно для Ш T




и У. Отсюда и появляется 23.T TP
T TP




2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединеныT скобками, а
T T




«свободны». Это даст нам 8! 22 вариантов, но мы должны исключить отсюда результат пунктаT 1, чтобы не
TP
T T T TP T T




сосчитать некоторые перестановки дважды. Получаем 120 960.T

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




5. Но мы можем рассмотреть (Ан, Ан) Ш Ш У У Ф Ит Ис Ам, где и Ш, и У «свободны». Это даст намT 9! 2
T T T T




случаев, из которых мы должны вычесть результаты пунктов 1, 2 и 3 по очевидным теперь причинам.T Получим
T T




443 520.T

6. Когда в скобки заключены только Ш, вычтем результаты пунктов 1, 2 и 4. ПолучимT 443 520.T
T T




7. Когда в скобках оставлены только У, вычтем результаты пунктов 1, 3 и 4. Получим 443 520.T
T




Сложим результаты семи пунктов и получим при этом 1 733 760. Теперь из самого первого результатаT
T




вычтем полученное число, что даст нам верный ответ, равный 1 895 040 способам.T
T




436. Головоломку можно решить за 9 переправ следующим образом:T
T


<< Предыдущая

стр. 40
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>