Величайшие математические задачи - читать онлайн книгу. Автор: Йен Стюарт cтр.№ 25

Это внушает оптимизм. До сих пор, насколько нам известно, для раскраски некоторых карт могло потребоваться 20 цветов, или 703, или несколько миллионов. Теперь мы знаем, что такие карты не более реальны, чем горшок золота под концом радуги. Мы знаем, что конкретного ограниченного числа красок точно хватит на любую карту. Это настоящий триумф метода минимальных контрпримеров. Математики, посмотрев на него, взялись за дело с еще большим энтузиазмом, надеясь усилить аргументацию и постепенно заменить шесть красок на пять, а если повезет, и на четыре.

Юристы иногда тоже интересуются математическими задачами. Адвокат по имени Альфред Кемпе присутствовал на том заседании, где Кейли упомянул задачу о четырех красках. В свое время он под руководством Кейли изучал математику в Кембридже, и за годы его интерес к этой науке нисколько не ослаб. Не прошло и года после заседания, а Кемпе уже убедил себя, что ему удалось справиться с задачей. Свое решение он опубликовал в 1879 г. в недавно основанном журнале American Journal of Mathematics. Еще через год он опубликовал упрощенное доказательство, где были исправлены некоторые ошибки, присутствовавшие в первом. Вот как он подошел к вопросу: «Очень небольшое изменение в части карты может привести к необходимости перекрашивать ее целиком. В результате достаточно сложного поиска мне удалось отыскать слабое звено, которое позволило одержать победу».

Я изложу идеи Кемпе в терминах двойственной сети. Опять же он начал с формулы Эйлера и следующего из нее вывода о существовании точки с тремя, четырьмя или пятью соседями. (Точка с двумя соседями лежит на линии и никак не влияет на структуру сети или карты: на нее можно просто не обращать внимания.)

Если существует точка с тремя соседями, то процедуру, которую я использовал для доказательства теоремы о шести красках, можно применить и к четырехкрасочному варианту. Удаляем саму точку и линии, которые в ней сходятся, раскрашиваем в четыре краски результат, возвращаем точку и линии на место и окрашиваем ее в оставшийся свободным цвет. Поэтому мы можем считать, что точки с тремя соседями не существует.

Если существует точка с четырьмя соседями, то вышеописанная методика не срабатывает, потому что при возвращении точки свободного цвета может и не оказаться. Кемпе придумал хитрый способ обойти это препятствие: он предложил так же точно удалить точку, но после этого поменять расцветку получившейся меньшей карты так, чтобы два из четырех ее бывших соседей получили один и тот же цвет. После такой модификации у соседей удаленной точки окажется не больше трех цветов — и в нашем распоряжении окажется свободный четвертый. Основная идея перекраски схемы по Кемпе заключается в том, что две соседние точки должны быть разных цветов — скажем, синего и красного, а еще в схеме используются зеленый и желтый. Если обе оставшиеся точки окажутся зелеными или желтыми, то второй цвет окажется свободным и может быть использован для удаленной точки. Исходя из этого, считаем, что одна из них зеленая, а вторая — желтая. Теперь найдем все точки, которые соединены с синей точкой последовательностью линий, проходящих только через синие и красные точки, и назовем их красно-синей цепочкой Кемпе ^{19}. По определению, любой сосед любой точки в цепочке Кемпе, не принадлежащий цепочке, должен быть зеленым или желтым, поскольку синий или красный сосед там уже есть. Обратите внимание, что замена цветов в пределах цепочки Кемпе (синий на красный, и наоборот) дает новый вариант карты, в которой по-прежнему выполняется ключевое условие о том, что соседние точки должны быть разных цветов (см. рис. 11).

Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет — и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьте: она не сможет замкнуться на желтого соседа, поскольку на ее пути непременно встретится предыдущая красно-синяя цепочка. Поменяйте желтый и зеленый цвета в цепочке местами, и дело сделано.

Остается последний случай: когда не существует точек с тремя или четырьмя соседями, но по крайней мере одна точка имеет пять соседей. Кемпе предложил аналогичное, но более сложное правило перекраски точек, которое, на первый взгляд, успешно решало и эту проблему. Вывод: теорема о четырех красках верна, и доказал ее Кемпе. Эта заявление попало даже в средства массовой информации: американский журнал The Nation упомянул решение Кемпе в своем обзоре.

Казалось, с проблемой четырех красок было покончено, и математики в большинстве своем с этим согласились. Правда, Питер Тэт продолжал поиски более простого решения и время от времени публиковал статьи на эту тему. Исследования привели его к нескольким полезным открытиям, но простое доказательство по-прежнему не давалось.

И тут на сцене появляется преподаватель математики из Университета Дарема Перси Хивуд, прозванный за свои великолепные ухоженные усы «Котом». Еще студентом в Оксфорде он услышал от профессора геометрии Генри Смита о теореме о четырех красках. Смит сказал ему, что теорема эта, хотя, вероятно, и верна, но не доказана, так что у Хивуда есть шанс. Кроме того, как-то он наткнулся на статью Кемпе и попытался ее понять. Результат своих размышлений Хивуд опубликовал в 1889 г. под названием «Теорема о раскраске карты», высказав при этом сожаление, что цель его статьи более «деструктивна, чем конструктивна, ибо в ней будет показано, что в признанном, кажется, на сегодня доказательстве есть дефект». Кемпе допустил ошибку.

Ошибка была достаточно тонкой и возникала в схеме перекраски в том случае, когда у удаляемой точки было пять соседей. В некоторых случаях изменение цвета одной точки (по схеме Кемпе) могло повлечь за собой невозможность дальнейших изменений. При этом Кемпе считал, что если какая-то точка меняет цвет, то происходит это лишь один раз. Хивуд же нашел карту (или сеть), в которой схема перекраски по Кемпе не срабатывала, и тем самым опроверг его доказательство. Кемпе, узнав об этом, без промедления признал ошибку и добавил, что ему «не удалось исправить этот дефект». Теорема о четырех красках вновь ждала желающих помериться с ней силой.

Хивуд отыскал в этой истории небольшое утешение для Кемпе: его метод успешно доказывал теорему о пяти красках. Кроме того, Хивуд работал еще над двумя обобщенными вариантами задачи: над вариантом с империями, где области могли состоять из нескольких несвязанных кусков, которые все требовали одного цвета, и над картами на более сложных поверхностях. Аналогичная задача на сфере решается точно так же, как на плоскости. Представьте себе карту на сфере, причем разверните сферу так, чтобы Северный полюс оказался внутри одной из областей. Теперь, если удалить точку полюса, то сферу с отверстием можно развернуть в поверхность, топологически эквивалентную бесконечной плоскости. Регион, в котором находился полюс, развернется в бесконечное пространство, окружающее карту. Однако, помимо сферы, существуют и другие, более интересные поверхности. Среди них тор, напоминающий по форме бублик с дыркой (см. рис. 12 слева).