Să presupunem că pe o coală de hârtie am desenat harta judeţelor ţării, urmând acum să le colorăm. Ni se cere o condiţie: niciu judeţ să nu aibă aceeaşi culoare cu unul vecin. Se poate realiza asta având la dispoziţie doar patru culori?

Presupun ca da

Desigur, iti dau un exemplu: Targu Jiu (Rosu), Valcea (Verde), Arges (Galben) si tot asa.

Nu se poate in toate cazurile, exista judete cu mai mult de 3 judete vecine, mai ales judetele din interiorul tarii. Puteai vedea asta pe o harta cu judetele.

Si primul judet nu este colorat?
Sigur ca se pot colora cu 4 culori dar culorile se vor repeta. Eu intelesesem ca nu trebuie sa se repete.

Nu trebuie sa se repete la doua judete vecine. Daca nu trebuia sa se repete deloc pe harta nici nu mai avea rost intrebarea pentru ca toata lumea cred ca stie ca sunt mai mult de 4 judete in tara noastra.

N-am spus ca deloc pe harta, doar la judetele vecine.

Http://www.geotutorials.ro/......maniei.png

Chiar orice harta? Oricat de complicata?

Se poate. Daca nu poti face o combinatie intre doua din cele patru culori, poti face anumite texturi dintr-o singura culoare sau mai multe (linii drepte verticale, oblice, sau orizontale, sau o combinatie intre cele trei). Si atunci poti face chiar si dintr-o singura culoare intreaga harta, daca esti un pic creativ la realizarea texturilor. Chestia asta se mai face la creerea hartilor, inainte, cand tiparul se limita la redarea a doar cateva nuante, asta sigur era o modalitate de compunere a hartilor.

Este adevarat si ce ai scris tu, dar eu m-am referit la coloratul simplu, fara dungi sau nuante.

O intrebare exceptionala! Asta e o dilema cu care se ocupa specialistii din ML (machine learning - domeniu care se ocupa cu inteligenta artificiala). Iti recomand sa urmaresti urmatorul videoclip pentru o intelegere mai buna a problemei: https://www.youtube.com/......tps?/watch

Si Gorjul, cu ce culoare?

Este intr-adevăr o problemă celebră. E interesant de urmărit povestea ei. Începută undeva pe la mijlocul secolului 19, a rămas nerezolvată mulţi ani, peste un secol, timp în care şi-au bătut capul cu ea matematicieni de elită. La un moment dat matematicianul P.J. Heawood a găsit un rezultat interesant cum că probabilitatea să găsim o hartă cu mai mult de 36 de regiuni care să nu poată fi colorată cu patru culori este mai mică de 1 pe 10 la puterea zece mii (pentru comparaţie: Pământul nostru are cca 10 la puterea 52 atomi).
Mi-a plăcut video-ul.