Математические головоломки профессора Стюарта

– Не в таком аспекте, – раздраженно отмахнулся он. – Географ раскрасит области на карте в соответствии с политической обстановкой, не обращая внимания на соседство. Смотрите, Кения, Уганда и Танганьика расположены рядом, но на всех картах Британской империи все они окрашены в одинаковый розовый цвет.

Я признал справедливость этого утверждения. Нашей дорогой королеве не понравилось бы, если бы их раскрасили иначе.

– Но, Сомс, – я продолжал настаивать, – вопрос от этого не становится менее интересным. Даже более, поскольку никто, похоже, не в состоянии на него ответить.

Сомс что-то проворчал.

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

– Забавно, – заметил Сомс. – А почему вы сделали все области круглыми?

– Потому что любая область без дырок топологически эквивалентна кругу.

Сомс поджал губы.

– Тем не менее это плохой выбор, Ватсап.

– Почему? Мне кажется…

– Ватсап, вам много что кажется, но мало что на самом деле имеет место быть. Хотя любая отдельная область топологически равноценна кругу, две или большее число областей могут перекрываться способом, невозможным для двух или нескольких кругов. Об этом свидетельствует тот факт, что для вашей карты достаточно всего двух красок, – и он заштриховал примерно половину областей.

– Ну да, но я уверен, что более сложная карта того же рода…

Сомс покачал головой.

– Нет-нет, Ватсап. Любая карта, состоящая исключительно из круглых областей, даже если эти области разных размеров и перекрываются разными, сколь угодно сложными способами, может быть раскрашена в две краски. Считая, как обычно и делается в подобных вопросах, что «соседние» области должны иметь общие участки границы, а не отдельные изолированные общие точки.

У меня отвалилась челюсть.

– Теорема о двух красках! Поразительно! – Сомс соизволил пожать плечами. – Но как такую теорему можно доказать?

Сомс откинулся в кресле.

– Вы знаете мои методы.

Ответ см. в главе «Загадки разгаданные».

Теорема о четырех красках в пространстве

Сомс говорил о знаменитой теореме о четырех красках, которая гласит, что для любой заданной карты на плоскости ее области можно раскрасить не более чем четырьмя разными красками так, чтобы области, имеющие общую границу, были окрашены в разные цвета. (Здесь «иметь общую границу» означает, что общая граница должна быть ненулевой длины; то есть если области сходятся в одной общей точке, это не считается.) Такое предположение высказал в 1852 г. Фрэнсис Гутри и доказали в 1976 г. Кеннет Аппель и Вольфганг Хакен при активном использовании компьютера[32]. За прошедшее с того момента время их доказательство удалось серьезно упростить, но компьютер по-прежнему является существенной его частью; он необходим, чтобы проводить большое количество рутинных, сложных вычислений.

Могут ли существовать аналогичные теоремы для «карт» в пространстве, а не на плоскости? Области в пространстве будут представлять собой что-то вроде заполненных пузырей. Немного подумав, несложно догадаться, что для раскрашивания такой карты может потребоваться сколько угодно красок. Представьте, к примеру, что вы хотите нарисовать карту, для которой нужно шесть красок. Для начала возьмите шесть отдельных шаров. Пусть шар 1 выпустит пять тонких щупалец и коснется ими шаров 2, 3, 4, 5 и 6. Затем пусть шар 2 выпустит пять щупалец и коснется шаров 3, 4, 5 и 6. Затем перейдите к шару 3 и т. д. Получится, что каждая обросшая щупальцами область касается всех остальных областей и, следовательно, все шесть должны быть окрашены в разные цвета. Если проделать такую процедуру со 100 шарами, то потребуется 100 красок; если шаров будет миллион, красок тоже потребуется миллион. Короче говоря, числу необходимых красок нет предела.

В 2013 г. Баскар Багчи и Басудеб Дата[33] поняли, что это не конец истории. Представьте себе «карты», сформированные из конечного числа кругов на плоскости, которые либо вообще не перекрывают друг друга, либо пересекаются в одной общей точке. Предположим, вы хотите раскрасить эти круги так, чтобы даже соприкасающиеся круги были окрашены в разные цвета. Сколько красок вам потребуется? Оказывается, ответ здесь такой же: не больше четырех.