# Câte culori îți trebuie ca să colorezi harta României Un joc cu creioane și o întrebare din 1852 Două județe care au graniță comună nu pot avea aceeași culoare. Ai trei creioane. Alege unul și apasă pe un județ. ## Harta fără hartă Ca să răspunzi la întrebare, poți uita forma județelor. Contează doar cine se învecinează cu cine. Pune un punct în fiecare dintre cele 41 de județe și unul în București, apoi trage o linie pentru fiecare graniță comună: ies 42 de puncte și 102 linii. Brașovul are cele mai multe, opt. O graniță scurtă contează cât una lungă: Buzăul și Brașovul se ating pe 2,3 km, Vasluiul și Vrancea pe 3,5 km, și tot nu pot avea aceeași culoare. Un singur punct comun nu contează deloc. Două țări care se ating doar într-un colț pot avea aceeași culoare. Altfel, o plăcintă tăiată în multe felii, care se ating toate în mijloc, ar cere câte o culoare pentru fiecare felie. Desenul de puncte are o proprietate pe care o are orice hartă cu țări dintr-o singură bucată: liniile lui pot fi trase fără să se încrucișeze. Matematicienii îi spun graf planar. Așa se poate pune întrebarea pentru orice hartă cu țări dintr-o bucată: îi ajung fiecărui graf planar patru culori? ## Între întrebare și dovadă au trecut 124 de ani - **1852.** Francis Guthrie colorează o hartă a Angliei și bănuiește că patru culori ajung pentru orice hartă. Fratele lui, Frederick, duce întrebarea la profesorul lor, Augustus De Morgan. Pe 23 octombrie, De Morgan îi scrie lui William Rowan Hamilton. Hamilton răspunde că nu o să încerce prea curând „cuaternionul” de culori. - **1878.** Arthur Cayley întreabă la Societatea de Matematică din Londra dacă problema fusese rezolvată. În anul următor, avocatul Alfred Kempe publică o demonstrație. - **1890.** Percy Heawood găsește greșeala din demonstrația lui Kempe, la unsprezece ani după publicare. Din ea se poate salva o dovadă că cinci culori ajung mereu. - **1976.** Kenneth Appel și Wolfgang Haken, de la Universitatea Illinois, reduc problema la aproape o mie cinci sute de configurații și pun un calculator să le verifice. O parte din dovadă e munca calculatorului și nu poate fi verificată de mână. - **1997.** Neil Robertson, Daniel Sanders, Paul Seymour și Robin Thomas publică o dovadă mai simplă: 633 de configurații și 32 de reguli. Tot de calculator e nevoie. - **2005.** Georges Gonthier și Benjamin Werner pun programul Coq să controleze fiecare pas al dovezii, inclusiv partea lăsată până atunci programelor scrise anume pentru ea. ## Și comuna ta are un inel? Sub cele 41 de județe și București sunt 3.181 de comune, orașe și municipii (Bucureștiul e socotit aici o singură unitate). Între ele sunt 9.251 de granițe. Inelul impar, care la județe apare de zece ori (în jurul Mureșului, Bacăului, Ilfovului și al altor șapte), apare aici la 1.537 de unități, aproape jumătate. Fiecare dintre ele, singură cu vecinii ei, cere deja patru culori. ## Unde teorema nu mai spune nimic Teorema celor patru culori are o condiție despre care la școală nu se vorbește de obicei: fiecare țară trebuie să fie dintr-o singură bucată. În limitele oficiale ale unităților (ANCPI), 39 de comune, orașe și municipii nu sunt. Un caz cunoscut e Păltinișul. Stațiunea din munți aparține municipiului Sibiu, dar între ea și oraș sunt alte comune. Lângă ea, Cristianul și Poplaca au câte trei bucăți, iar Săliștea două. Uite ce iese de aici. Sibiul, Cristianul și Gura Râului au, fiecare, graniță cu Rășinari, cu Poplaca și cu Orlatul. Doar Sibiul ajunge la Orlat ocolind, prin Șura Mică și Săliște. Cea mai scurtă dintre aceste granițe are 4,6 km, deci nu e o eroare de desen. Este vechea ghicitoare cu trei case și trei fântâni: leagă fiecare casă de fiecare fântână fără ca două drumuri să se încrucișeze. Încearcă mai jos. În 1930, Kazimierz Kuratowski a arătat că există doar două motive pentru care un desen de puncte și linii nu poate fi făcut plat, iar acesta, cu trei case și trei fântâni, e unul dintre ele. Pe hartă merge pentru că patru dintre ele, Sibiul, Cristianul, Poplaca și Săliștea, sunt în mai multe locuri deodată. Percy Heawood se gândise la asta încă din 1890: dacă fiecare țară poate avea două bucăți, unele hărți cer douăsprezece culori, iar douăsprezece ajung mereu. Dintre cele 39 de unități din bucăți, la 24 e de ajuns una singură, unită, ca desenul comunelor să nu mai poată fi făcut plat. ## Patru ajung, totuși Pentru comunele României, teorema nu mai garantează nimic. Rămâne doar să încerci. Apasă butonul, iar calculatorul sau telefonul tău caută acum, sub ochii tăi, o colorare a celor 3.181 de unități cu patru culori. Pornește de la o colorare făcută în grabă, unitate cu unitate, care lasă vecini cu aceeași culoare. Apoi, pas cu pas, schimbă culoarea unei unități care are un vecin de aceeași culoare. Când se împotmolește, o ia de la capăt. Trei culori nu ajung nici aici: oricare dintre cele 1.537 de inele impare o arată. Așa că răspunsul pentru România, de la județe până la ultima comună, e același: patru. Pentru comune, l-a dat o căutare, nu teorema. ## Colorează-ți județul Alege un județ și tipărește-l. Ai nevoie de patru creioane: niciunul dintre cele 41 de județe nu se poate colora cu trei, nici măcar luat singur. Bucureștiul, socotit aici o singură unitate, se colorează cu un singur creion. ## Cum s-a numărat Granițele vin din limitele unităților administrativ-teritoriale ale ANCPI, versiunea din 26 martie 2025, prelucrate de geo-spatial.org în format TopoJSON, unde două unități vecine au aceeași linie de graniță. Două unități sunt vecine când au în comun o bucată de linie, nu doar un punct. Bucățile de graniță mai scurte de 100 de metri, de obicei colțuri în care se întâlnesc patru unități, desenate cu mici abateri, nu sunt socotite. Cu ele, inelele impare ar fi 1.594. Fără granițele sub 500 de metri, ar fi 1.320. Colorarea din imaginea de prezentare a paginii respectă și granițele foarte scurte; căutarea din pagină le ignoră pe cele sub 100 de metri. Un inel impar înseamnă că vecinii unei unități nu se pot colora cu două culori. Atunci unitatea și vecinii ei au nevoie, împreună, de patru. Pentru fiecare unitate e arătat cel mai scurt astfel de inel. Faptul că desenul de puncte al comunelor nu poate fi făcut plat e verificat pe rețeaua de granițe: dacă fiecare bucată despărțită e socotită unitate separată, desenul e plat; unite, nu mai e. Ghicitoarea de la Sibiu e un exemplu găsit de calculator, cu toate granițele de cel puțin 4,6 km. Același număr de bucăți (trei la Cristian, trei la Poplaca, două la Sibiu) apare și în OpenStreetMap. Căutarea din pagină folosește căutarea tabu pentru colorări, descrisă de Alain Hertz și Dominique de Werra în 1987: schimbă culoarea care strică cel mai puțin și ține minte câțiva pași ce a schimbat, ca să nu se întoarcă imediat. Ea nu dovedește că o colorare nu există. Pentru trei culori, dovada vine din inelele impare. ## Surse - [ANCPI, limitele unităților administrativ-teritoriale, prelucrate de geo-spatial.org (versiunea 2025-03-26), CC BY 4.0](https://geo-spatial.org/descarcare/date/administrative-boundaries/) - [Robin Wilson, Four Colors Suffice (Princeton University Press), capitolul despre 1852: scrisoarea lui De Morgan și răspunsul lui Hamilton](https://press.princeton.edu/books/paperback/9780691158228/four-colors-suffice) - [MacTutor, The four colour theorem (Cayley, Kempe, Heawood, Appel și Haken)](https://mathshistory.st-andrews.ac.uk/HistTopics/The_four_colour_theorem/) - [Robertson, Sanders, Seymour, Thomas, The four-colour theorem, J. Combin. Theory B 70 (1997)](https://thomas.math.gatech.edu/PAP/fc.pdf) - [Robin Thomas, The Four Color Theorem (pagina dovezii din 1997)](https://thomas.math.gatech.edu/FC/fourcolor.html) - [Georges Gonthier, A computer-checked proof of the Four Colour Theorem (enunțul exact: țări dintr-o bucată, colțurile nu contează)](https://www.cl.cam.ac.uk/~lp15/Pages/4colproof.pdf) - [Microsoft Research, Gonthier și Werner, verificarea în Coq (2005)](https://www.microsoft.com/en-us/research/blog/theorem-proof-gains-acclaim/) - [MathWorld, Empire Problem (Heawood: 6m culori ajung pentru țări din m bucăți)](https://mathworld.wolfram.com/EmpireProblem.html) - [MacTutor, Percy Heawood (greșeala lui Kempe, hărțile cu țări din două bucăți și cele 12 culori)](https://mathshistory.st-andrews.ac.uk/Biographies/Heawood/) - [OpenStreetMap, granițele administrative ale comunelor Cristian, Poplaca și ale municipiului Sibiu](https://www.openstreetmap.org/relation/9846495)