Теоремата за четирите цвята: Защо тя остана недоказана в продължение на 124 години

През 1852 г. Франсис Гътри оцветявал карта на Англия, като искал съседните графства да бъдат в различни цветове. Докато правил това, той открил закономерност: три цвята били недостатъчни, пет били повече от достатъчни, а четири, очевидно, били достатъчни за всяка карта. Той обаче не могъл да обясни защо е така. Това наблюдение поражда математическа загадка, която озадачавала учените в продължение на 124 години.

Гътри учил при известния математик Огъстъс де Морган в Университетския колеж в Лондон и чрез брат си Фредерик му предал въпроса си. Де Морган бил озадачен. На 23 октомври 1852 г. той написал писмо до ирландския математик Уилям Хамилтън. Проблемът звучел почти като училищна гатанка – и това се превърнал в основния му капан. Той привличал всички, създавал илюзията за решение и отблъсквал всеки опит, един след друг.

Фундаменталното ограничение на проблема беше концепцията за „съседство“. Два региона се считат за съседни само ако споделят обща граница. Регионите, които се докосват в една точка, не се считат за съседи – една точка не е достатъчна. Това означава, че картата не може да бъде структурирана като шахматна дъска, където всяко квадратче има осем съседа. Тук структурата е по-проста. Именно тази простота дълго време сякаш подсказваше, че проблемът може да бъде решен във възможно най-кратки срокове.

Единадесет години триумф

През 1879 г. лондонският адвокат и математик-любител Алфред Кемп обявява, че проблемът е решен. Доказателството му е публикувано в списанието Nature, едно от най-авторитетните научни издания на епохата. Методът му се основава на това, което по-късно е наречено „вериги на Кемп“: свързани групи от региони с един и същи цвят, които могат да бъдат преоцветени, без да се нарушава правилото за съседство. Колегите му намират идеята за елегантна и завладяваща, а математическата общност приема работата: проблемът на Гътри се счита за решен.

Кемп става член на Кралското общество в Лондон, а през 1912 г. получава рицарско звание. В продължение на единадесет години никой по света не открива недостатък в разсъжденията му. Всъщност, недостатък е имало – и той е чакал своя момент.

Дупка в аргумента на някой друг

През 1890 г. младият математик от Дърам, Пърси Хийууд, внимателно анализира доказателството на Кемп и идентифицира конкретна точка, където аргументът се проваля. За карти, в които един регион има пет съседа, верижният метод се разпада: два цикъла на прерисуване могат да се припокриват и взаимно да се неутрализират. Кемп не успява да затвори тази празнина.

Хийууд публикува анализ и доказва по-слабо твърдение: пет цвята винаги са достатъчни за всяка карта. Дали четири биха били достатъчни остана загадка. Дебатът, привидно приключен, беше отворен отново, но къде да се намери нов отговор, не беше ясно.

Осемдесет и шест години прекаляване

През следващите осемдесет и шест години проблемът остава нерешен. Американският математик Джордж Биркхоф въвежда концепцията за „редуцибилна конфигурация“ – фрагмент от карта, който може да бъде опростен. Това е правилният подход: ако можехме да докажем, че всяка карта задължително съдържа поне една такава конфигурация и че всяка конфигурация може да бъде опростена и преоцветена, проблемът ще бъде решен. Проблемът оставаше с мащаба. Необходими бяха хиляди конфигурации и проверката на всяка една ръчно беше нереалистична.

През 1969 г. немският математик Хайнрих Хееш доразвива метода и въвежда техниката на „разреждане“ – начин за разпределяне на определен формален заряд по картата, за да се идентифицират проблемни области. Хееш изчислява, че пълното доказателство би изисквало проверка на приблизително 8900 конфигурации – задача, която никой не би могъл да изпълни ръчно за разумен период от време: задачата се превръща в груба сила.

1200 машинни часа

До 1976 г. математиците Кенет Апел и Волфганг Хакен от Университета на Илинойс са събрали пълен набор от 1482 „неизбежни конфигурации“ – фрагменти, поне един от които се появява във всяка възможна карта. Това е доказано математически. Всяка конфигурация след това е тествана поотделно: всяка от тях може да бъде редуцирана до по-проста карта и преоцветена с четири цвята, без да се нарушават правилата. Тази стъпка е извършена от компютър. Машината е работила 1200 часа.

Логиката е следната: тъй като всяко изображение съдържа поне една неизбежна конфигурация и всяка от тях може да бъде опростена без проблеми с оцветяването, четири цвята винаги са достатъчни. Апел и Хакен обявиха доказателството си на 21 юни 1976 г. 124 години бяха изминали от първия въпрос на Гътри.

Доказателство, което не може да бъде проверено ръчно

Но беше твърде рано за празнуване. Математиците бяха свикнали с доказателства, които колега можеше да провери стъпка по стъпка. Тук това беше невъзможно: ключовата част от аргумента съществуваше само в паметта на машината и ръчното ѝ възпроизвеждане означаваше загуба на хиляди часове компютърно време – не само препрочитане на текста.

Критиците зададоха директен въпрос: как могат да бъдат сигурни, че програмата е без грешки? Авторите възразиха: как могат да бъдат сигурни в ръкописно доказателство, дълго стотици страници – то може да съдържа и грешки. Теоремата стана първият важен математически резултат, доказан с помощта на компютър, и повдигна въпрос, на който по това време нямаше ясен отговор: какво представлява валидно доказателство в математиката.

През 1997 г. независим екип – Нийл Робъртсън, Даниел Сандърс, Пол Сиймур и Робин Томас – конструира по-опростена версия на доказателството с 633 конфигурации и код с отворен код, който всеки може да провери. Въпреки че съмненията не бяха напълно разсеяни, теоремата влезе в учебниците като доказана.

2026: Още доказателства

През март 2026 г. група математици – датските математици Микел Труп и Карстен Томасен, японският математик Кен-ичи Каварабаяши и канадският математик Боян Мохар – публикуваха ново доказателство . То тества 8202 конфигурации – тринадесет пъти повече от версията от 1997 г. – но предоставя фундаментално по-бърз алгоритъм за оцветяване на карти.

Предишният метод изискваше брой стъпки, пропорционални на квадрата на броя региони: за карта от милион региона това означаваше приблизително милион операции на регион. Новият алгоритъм постига това с брой стъпки, пропорционални на милион пъти логаритъма от милион – приблизително 50 000 пъти по-малко за същия мащаб на картата.

Проблемът на Гътри има практически приложения: същите алгоритми за оцветяване работят при проблеми с радиочестотното планиране, разписанието и разпределението на ресурсите на процесора. Но основното значение на теоремата се крие другаде. В продължение на 124 години тя демонстрира, че „очевидно“ и „доказано“ не са едно и също нещо. Ученикът на Гътри е бил прав, когато е задал въпроса си през 1852 г. Между неговото наблюдение и доказателство се намират век работа, един фалшив триумф и първият компютърно подпомогнат аргумент в историята на математиката.