Ознакомительная версия. Доступно 22 страниц из 110
в занятном положении. Возьмем карту, которая может оказаться минимальной криминальной. Выберем любую область и сожмем ее в точку. Это уменьшит количество областей на одну. Теперь у редуцированной карты не хватает областей, чтобы считаться криминальной, поскольку у нее на одну область меньше, чем у минимальной криминальной карты, с которой мы начали. Следовательно, редуцированная карта законопослушна, а значит, ее можно раскрасить четырьмя красками. Раскрасим ее.
Теперь обратим процесс. Вернем на карту область, которую мы сжали в точку – раздуем эту область обратно. Теперь у нас есть первоначальная карта, на которой как следует раскрашены все области, кроме той, которую мы сжали, а потом восстановили. Зададимся вопросом: есть ли способ раскрасить восстановленную область так, чтобы она вписалась в четырехцветовую схему, которую мы применили к редуцированной карты? Это, конечно, зависит от того, какую область мы выбрали для сжатия и восстановления. Если, например, была выбрана область, граничащая только с тремя другими, вам повезло: когда вы ее восстановите, из четырехцветной схемы останется один цвет, который отличит восстановленную область от трех соседок. Но тогда вы смогли раскрасить исходную карту четырьмя красками. Значит, предполагаемая минимальная криминальная карта вовсе не была криминальной!
Тогда очевидно, что карта, претендующая на звание минимальной криминальной, не должна содержать областей, граничащих только с тремя другими областями. Иначе (1) можно сжать такую область в точку, таким образом снизив число областей на одну и сделав так, чтобы карта оказалась ниже минимально-криминального порога и, следовательно, оказалась законопослушной, (2) раскрасить редуцированную законопослушную карту четырьмя красками, (3) затем восстановить сжатую область, раздув ее снова, и (4) раскрасить восстановленную область одним из четырех цветов, не совпадающим с цветами ее трех соседок, тем самым включив восстановленную область в четырехцветную схему. И тогда исходная карта в конце концов оказывается законопослушной.
Если карта поддается этому процессу сжатия-раскрашивания-восстановления, говорят, что у нее «редуцируемая конфигурация». Как мы только что видели, один их типов редуцируемой конфигурации – это область, граничащая только с тремя другими областями. Увы, такая область найдется не на каждой карте. Но, вероятно, есть и другие типы редуцируемых конфигураций. И, вероятно, можно показать, что любая карта, какой бы сложной она ни была, обязательно содержит хотя бы одну редуцируемую конфигурацию. Если да, это решило бы вопрос. Карта, содержащая редуцируемую конфигурацию, не может быть минимальной криминальной, такая карта всегда может быть раскрашена в четыре цвета в результате процесса сжатия-раскрашивания-восстановления. Так что если любая карта содержит хотя бы одну разновидность редуцируемой конфигурации, значит, минимальных криминальных карт не бывает. А если не бывает минимальных криминальных карт, значит, криминальных карт не существует, и точка. (Если криминальные карты существуют, среди них должны быть карты с минимальным числом регионов.) А если не существует криминальных карт, значит, любая карта законопослушна, то есть может быть раскрашена в четыре цвета.
∞
Именной этой логикой руководствовался и Альфред Брэй Кемп, лондонский адвокат и математик-любитель, который в 1879 году заявил, что доказал гипотезу четырех красок. Рассуждения Кемпа были полны математических хитростей, но показались убедительными, и не только Чарльзу Пирсу. Лучшие математики Британии, Континента и Соединенных Штатов признали, что перед ними долгожданное решение проблемы четырех красок. Кемпа приняли в Королевское общество, а затем и посвятили в рыцари. Его «доказательство» продержалось десять лет, пока в нем не обнаружили неочевидную, но фатальную ошибку. Нашел ее ученый-классик и математик Перси Хивуд, он же «Котик» Хивуд, как прозвали его друзья за роскошные усы.
Хивуд, который чуть ли не извинялся за то, что опроверг доказательство Кемпа, обладал некоторыми странностями характера, которые выделяют его даже среди героев этой саги, полной всевозможных чудаков и эксцентриков. Был он тощ и слегка сутул и, как правило, одевался в плащ с пелериной в необычных узорах и не расставался с древним саквояжем. Его повсюду сопровождала собака – даже на лекциях. Он любил заседать в ученых комитетах и считал, что день прошел зря, если он не поучаствовал хотя бы в одном заседании. Время на своих вечно отстававших часах он выставлял раз в год, в Рождество, а потом весь год подсчитывал в уме, какой нынче час. «Нет, они не на два часа спешат, а на десять часов отстают!» – уверял он коллегу. Однако были у него и практические таланты: когда Даремский замок XI века едва не сполз с утеса, на котором был построен, в реку Уир, Хивуд почти в одиночку собрал денег на его спасение.
А теперь еще одна математическая интерлюдия. Если доказать гипотезу четырех красок трудно, попробуем задачу попроще: так называемую гипотезу шести красок. Это аналог проблемы четырех красок, только, очевидно, слабее: гипотеза гласит, что для того, чтобы раскрасить любую возможную карту так, чтобы соседние области всегда были разного цвета, достаточно шести красок. Гипотеза шести красок достойна рассмотрения, поскольку выявляет математические корни проблемы четырех красок, восходящие к середине XVIII века и к великому швейцарскому математику Леонарду Эйлеру (чья фамилия на самом деле произносится «Ойлер»).
Эйлер, вероятно, был самым плодовитым математиком в истории. Среди открытий, которые он совершил, курсируя между дворами Фридриха II и Екатерины II, была формула V-E+F=2; недавно ее признали второй по красоте теоремой в математике. (Победителем конкурса красоты, по данным опроса 1988 года в журнале Mathematical Intelligencer, стало тождество e=-1)[16]). Формула Эйлера описывает любой многогранник, то есть любое тело, ограниченное плоскими поверхностями, вроде куба или пирамиды. Она гласит, что если сосчитать все вершины многогранника (V), вычесть количество ребер (E) и прибавить количество граней (F), в результате всегда получается 2. Например, у куба 8 вершин, 12 ребер и 6 граней. И в самом деле, 8-12+6=2.
Какое отношение многогранники имеют к картам? Если взять многогранник и после некоторых хирургических манипуляций развернуть его в плоскость, каждая грань будет похожа на область на карте. Напротив, из карты можно сшить многогранник. При этом формы и размеры областей изменятся, но это не повлияет на общую конфигурацию карты и на количество цветов, необходимых, чтобы ее раскрасить. Таким образом, проблема четырех цветов – это задача по топологии, отрасли математики, занимающейся свойствами, не меняющимися при растяжении и скручивании.
А теперь применим формулу Эйлера к карте. Тогда F – это число областей, E – число границ, а V – число точек пересечения этих границ. Теперь можно вывести результат, без которого невозможно подойти к проблеме раскрашивания: на каждой карте должна быть по крайней мере одна область, у которой не больше пяти непосредственных соседок. Доказать это достаточно просто. Если бы существовала карта,
Ознакомительная версия. Доступно 22 страниц из 110
