A négyszín-sejtést csak számítógéppel sikerült bebizonyítani

Számítógépet legelső alkalommal az úgynevezett négyszín-sejtés nevű feladvány megoldásában használták. A sejtést egy érdeklődő amatőr vetette fel elsőként: ha térképeket színezünk, akkor a szomszédos országokat más-más színnel kell megjelölni, és a tapasztalatok szerint ezt a feladatot mindig meg lehet úszni négy színnel.

A sejtés bebizonyítása azonban több mint száz évig váratott magára

1852-ben Francis Guthrie joghallgató egyik levelében azt kérdezte fivérétől, a University College London matematikusától, hogy bebizonyította-e már valaki, hogy négy szín mindig elegendő? Bár akkoriban senki tartotta fontos problémának, néhány matematikus megpróbált bizonyítást találni – ám mindegyikük kudarcot vallott. Idővel így egyre nagyobb respektje lett a feladványnak, sőt, több mint száz éven át nem sikerült bebizonyítani a feltevést – egészen 1976-ig, amikor az Illinoisi Egyetem két tudósa, Kenneth Appel és Wolfgang Haken kimutatta, hogy a probléma visszavezethető 1500 különböző alaptérképre. Ez volt a döntő lépés, hiszen belőlük így már az összes térkép megrajzolható. Ám kézzel kiszínezni mindegyiket természetesen nagyon sokáig tartott volna, így ők számítógép segítségével bizonyították be a feltevést – a matematika történetében először. A bizonyítás leírásához 800 gépelt oldalra volt szükség, a kompjúter pedig 1200 óra alatt számította ki, hogy minden térkép kiszínezéséhez ténylegesen elegendő mindössze négy szín. (A bizonyítást nagyon sok matematikus nem fogadja el, hiányolva a „klasszikus módszert”, ugyanakkor bár gyakorlati haszna nem volt, kiderült: akkoriban még nem értették eléggé a kétdimenziós teret.)

Andrásfai Béla: Hány szín kell a térkép színezéséhez?
Marcus du Sautoy: A prímszámok zenéje

  • agytoro.hu
    Érdekes és misztikus történek, feladványok, fejtörők, gondolkodásra késztető feladatok, közmondások, idézetek és egyéb fontos, hasznos és érdekfeszítő adatok.
Előző cikkFasírtban van vele? Faképnél hagyta? Megütheti a bokáját? Miért így mondjuk??
Következő cikkKolumbusz tojása egy olasz zsenihez kötődik