Ész Ventura: A húsvéti tojások kromatikus száma
A húsvéti tojások között a kakukktojást megtalálni nehéznek bizonyult, de nem volt lehetetlen. Néhány olvasónak sikerült, nekik ezúton is gratulálunk! Bár húsvéti tojások esetén természetes, nem volt véletlen, hogy mindegyik tojás ki volt festve, ugyanis a keresendő tulajdonság is a színezéssel volt kapcsolatos. Aki figyelmesen megnézte a tojások színezését, az észrevehette, hogy van valami közös az összes tojásban: nevezetesen az, hogy két szomszédos régió színe mindig különbözik. Innen már könnyedén jön a megoldás is, a kakukktojás az egyetlen tojás, amelyik több színnel van színezve, mint amennyi feltétlenül szükséges lenne (ez az ún. kromatikus szám) ahhoz, hogy teljesítse a fenti feltételt. Így már kitaláljátok, hogy melyik a kakukktojás? Nem más, mint a legalsó sorban balról a harmadik tulipános tojás. Alább láthatjátok, hogy négy szín helyett három szín is elegendő a színezéséhez. A térhatású illuszrációt Békési István megoldónak és a Windows 10 Paint 3D programjának köszönhetjük.
Egyébként volt olyan tojás is, ahol négy szín feltétlenül szükséges volt, például a kakukktojás fölötti tojás. Hogy ennél négy szín szükséges, azt könnyű belátni, hiszen találunk a tojáson négy olyan régiót, amelyek mindegyike érinti a másik hármat. Ilyen például bármelyik egymás melletti fehér és piros csík, és az azon a tojásféltekén lévő kék és zöld régiók. De vajon lehetséges-e olyan mintázat, hogy négy szín ne legyen elegendő a színezéséhez, vagyis a kromatikus szám nagyobb legyen négynél? A válasz az, hogy nem. Ezt mondja ki a híres négyszín-tétel, ami sokáig csak sejtés volt, és nem is sikerült embereknek önállóan bizonyítani, ugyanis ez volt az első nevezetes sejtés a matematika történetében, amit számítógép segítségével sikerült bizonyítani.
A tétel egyébként eredetileg síkbeli színezésről szól. Pontosan úgy szól az állítás, hogy egy tetszőleges régiókra osztott síkot, azaz térképet, ki lehet úgy színezni legfeljebb négy szín felhasználásával, hogy ne legyen két azonos színű szomszédos régió. Két régiót akkor nevezünk szomszédosnak, ha legalább egy görbe mentén érintkeznek. Kikötés még, hogy a régióknak összefüggőknek kell lenniük, tehát nem állhatnak különálló részekből, mint sok ország a valóságban, például az USA. Egyébként segítségnek azért említettem a Kétfarkú Kutyákat, mert nekik gyakran vannak olyan akcióik, hogy az elhanyagolt feltöredezett járdákon illusztrálják a négyszín-tételt.
Könnyen belátható azonban, hogy a tétel a gömbfelületen, így a tojáson is, éppúgy érvényes, mint a síkon, hiszen a gömbfelület egyetlen pont kivételével leképezhető a síkra folytonosan, például az ún. sztereografikus projekció alkalmazásával, de ha a kimaradó pontot egy régió közepébe választjuk, akkor az nem fog problémát okozni, hiszen a síkra levetített térképet kiszínezve, a neki megfelelő színezés a gömbön is ugyanúgy teljesíteni fogja a feltételeket.
Guthrie és Anglia megyéi
Kicsit visszatérve a tétel történetére, a sejtést először 1852-ben fogalmazta meg Francis Guthrie matematikus és botanikus, amikor megfigyelte, hogy Anglia megyéinek színezéséhez négy színnél nem volt többre szüksége. Több bizonyítás is született, melyek mindegyikéről kiderült később, hogy hibásak. Végül 1976-ban született meg az a sokak által vitatott bizonyítás, ami számítógép segítségével 1936 speciális esetre vezette vissza az ellenőrizendő térképek számát, amik ellenőrzését szintén számítógéppel hajtottak végre. A program 1200 órán keresztül futott, a teljes bizonyítás pedig sok száz kézzel írott oldalt, sok ezer számítógép által generált diagramot és több száz mikrokártyát tartalmazott.
Ez a bizonyítás azért váltott ki sok vitát, mert elvileg lehetséges, hogy a programba hiba csúszik, vagy a számítógép hardverében, esetleg a fordítóprogramban van hiba, amiről nem tudunk. Az is igaz azonban, hogy egy matematikus bizonyításába is csúszhat hiba, főleg, ha ilyen sok esetet kell megvizsgálni, mint ami a fenti sejtés esetén is szükséges volt. Valójában az eredeti bizonyításban mindkét hiba előfordulhatott volna, viszont 2004-ben sikerült a tétel teljes bizonyítását egy ún. tételbizonyító rendszerben formálisan leírni, ettől kezdve sokkal kisebb a hibalehetőség, és nagyobb lett a bizonyítás elfogadottsága, mert csak a tételbizonyítóban kell megbízni.