Eszter, Eliza
16 °C
29 °C

Egy biológus oldott meg egy olyan problémát, amire a matematikusok már 60 éve képtelenek

2018.05.04. 22:00

Legalábbis részben. A szabadúszó biológus és amatőr matematikus Aubrey de Grey pár hét alatt rájött arra, hogyan lehet közelebb jutni az 1950 óta megoldatlan Hadwiger-Nelson probléma megoldásához. Ha nagyon bulvárosan akarnánk fogalmazni: ámulnak most a matematikusok a tanulmánya és megoldása láttán! 

A Hadwiger-Nelson probléma lényege az, hogy mi pontokkal ki akarunk színezni egy sík felületet, mintha csak Painttel rajzolgatnák. Ez így elég egyszerűnek hangzik és az is, csak türelem kell hozzá, hogy minden fehér részt beszínezzünk a pontokkal. Igen ám, de mi van akkor, ha két pontot csak úgy rakhatunk egymás mellé, hogy legyen köztük egy centiméter távolság, és két szomszédos pont nem lehet ugyanolyan színű? Hány szín kell ilyenkor? Na, ez a nagy a kérdés.

Játék az egész

De Grey szerint, hogy jobban el tudjuk képzelni a dolgot, gondoljuk azt, hogy mi egy barátunkkal éppen nagyon unatkozunk. Nincs se tévé, sem telefon, sem internet, de még csak pénzünk sincs, hogy elmenjünk valahová. Mindössze két dolog áll rendelkezésünkre:

Papír és színes ceruza.

Ekkor a barátunk azt mondja: játszunk egy játékot (nem, ez nem a Fűrész). A játék lényege az, hogy ő pontokat rajzol a saját papírjára fekete ceruzával, mindegyik egy centiméter távolságra van a másikról (de bármelyik irányba), és egy vonallal is össze is köti őket. Nekünk le kell őt utánoznunk a saját papírunkon, de nálunk csak színes ceruza van, és az a szabály, hogy egymás mellett nem lehet két egyforma színű pont.

Nyilván, ha van 100 színes ceruzánk, akkor a barátunk akár meg is feszülhet, úgy is tudunk egymás mellé két különböző színű pontot rajzolni. Sőt, igazából hét színes ceruzával is lazán le tudjuk iskolázni a matematikai elméletek szerint. De mivel délután hazajönnek a gyerekek és színezni akarnak majd, ezért mi próbálunk minél kevesebb színes ceruzát elhasználni. A kérdés már csak az,

hány ceruzát kell használnunk, hogy biztosan nyerjünk?

Ha csak egy színt akarunk használni, akkor rettentő egyszerű a dolog, már a második pontnál megszívjuk, hisz csak egy színünk van, és egymás mellett nem lehet két egyforma. 

Ha két színes ceruzát próbálunk meg használni, akkor már egy kicsit a barátunknak is gondolkodnia kell. De tételezzük fel, hogy jó volt középiskolában geometriából, ezért úgy rajzol fel három pontot, hogy egy háromszöget kapjunk. Ekkor megint megszívjuk. 

Ha három színt tervezünk használni, akkor már tényleg nehéz dolga van a barátunknak: hét jól elhelyezett pont kell hozzá, hogy csapdába csaljon minket. Ha viszont már van négy ceruzád, akkor elvileg verhetetlen vagy, de csak elvileg.

Az amatőr zseniális megoldása

Eddig a pontig jutottak el a matematikusok, sőt arra is rájöttek, hogy hét színes ceruza biztos elég a sikerhez, tehát már csak azt kellett bebizonyítani, hogy 4, 5, 6 vagy 7 ceruza kell a biztos győzelemhez. Azonban ezt nem tudták eddig eldönteni, de jött de Grey.

Ő  egy olyan, hét pontból és 11 vonalból (szárból/lapból/oldalból) álló alakzatot használt (lásd a fenti illusztráción), amit angolul Moser spindle-nek neveznek. Majd ezt más konfigurációkkal egyesítve rájött arra, hogy az így kapott 20 425 pontból álló konfigurációt egyszerűen nem lehet négy ceruzával kiszínezni. Az elképzelését később leellenőrizte egy erős számítógép segítségével, majd rájött, hogy igazából már 1 581 pont is elég a sikerhez.

Tehát bebizonyította, hogy a négy szín nem elég, így a probléma megoldásához legalább 5, 6 vagy 7 színes ceruzára van  szükség.

Röviden összefoglalva a probléma lényegét: a fent említett barátunknak olyan konfigurációt kell találnia, amit mi már nem tudunk kiszínezni. Nyilván, ha a barátunk teljesen fogalmatlan a matematikával kapcsolatban, akkor akár három színnel is le tudjuk győzni, ha viszont olyan okos (vagy szerencsés), mint de Grey, akkor 1 581 pont jó helyre rajzolása után legyőz minket akkor is, ha négy ceruzát használunk.

Fölül az 1581 pontból álló alakzat, alatta egy 1345 és egy 20425 pontból álló ún. vertex
Fölül az 1581 pontból álló alakzat, alatta egy 1345 és egy 20425 pontból álló ún. vertex

A matematikusok feladata tehát az, hogy olyan konfigurációkat találjanak, amikkel a barátunk le tudna minket győzni a játékban akkor is, ha öt vagy hat ceruzát használunk. Vagy, be kellene tudniuk bizonyítani, hogy nem létezik a pontok olyan kombinációja, hogy azt már öt vagy hat ceruzával ne tudnánk a szabályoknak megfelelően kiszínezni. A hét színes ceruza már bizonyítottan elég a sikerhez, a kérdés csak az, hogy mi a helyzet az öt- és hatceruzás felállásokkal.

15%
4999 Ft
4250 Ft
15%
2999 Ft
2550 Ft