Ördöglakat

Kétkezi logikai játékok a könnyűtől a szinte lehetetlenig.

Friss topikok

Golomb

2016.07.03. 17:02 Gál Péter F.

1954-ben megjelent a The American Mathematical Monthly-ban Solomon Golomb cikke "Checker Boards and Polyominoes" címmel és ezzel útjára indult a matematika és a játékok világának egy azóta is töretlenül fejlődő ága. Sajnos a cikk nehezen hozzáférhető, de álljon itt két oldal belőle:

cikklapok.png

Ennek a cikknek a fogadtatása is megmutatta, hogy mekkora igény van a szemléletes, játékos, kézzel fogható matematikára. A poliominók, de főleg a pentominók szinte azonnal közkedveltek és népszerűek lettek, nemcsak játékboltokban jelentek meg, de számos iskola bevette az oktatást kiegészítő "taneszközök" közé.

Golomb számos felkérést kapott a előadások tartására, újabb problémák, játékos feladványok kitalálására. Több cikket írt a témában, majd 1964-ben megjelent az első könyve, amely részletesen tárgyalta az addig megismert poliominókkal kapcsolatos tényeket. A szigorú matematikán kívül számos jópofa, akár általános iskolás szinten is tárgyalható feladványt közöl. Mint a jó matek könyvekben szokásos, több megoldatlan, rendkívül nehéznek tűnő problémát is bemutat, biztatva az olvasókat ezek megoldására, de újabbak kitalálására is.

Az első kiadás hamar elfogyott, így egyre nagyobb igény merült fel az újra kiadására. Golomb kicsit más utat választott. A második kiadás az első apró hibáinak javításán kívül több új fejezettel is bővült, többek közt az időközben megoldott problémák ismertetésével és néhány újonnan vizsgált terület ismertetésével. Nagy örömömre ebből a kiadásból én is rendelkezem egy dedikált példánnyal.

Annak szemléltetésére, hogy milyen frappáns, ötletes megoldások szerepelnek a könyvben, álljon itt egy rövid állítás és a bizonyítása belőle!

Foglalkoztunk már a pentominó elemek sakktáblán történő elhelyezésével. Abban a bejegyzésben láthattuk, hogy a sakktábla lefedhető a 12 pentominóval és még a négyzet alakú tetrominóval (más szóval: a pentominós lefedésből kimaradhat egy 2×2-es négyzet). Láttuk, hogy ez a négyzet lehet a tábla közepén, vagy a sarkán. De lehet-e még máshol is? Esetleg lehet-e bárhol? Golomb megmutatta, hogy igen! Az állítás tehát:

Akármelyik 2×2-es négyzetet vágjuk ki a sakktáblából, a maradék mezők lefedhetők a 12 pentominóval.

A 12 pentominó már sokszor szerepelt a blogon, azért következzen megint a képük:

pentominoelemek.png

Mindegyik 5 négyzetből áll, tehát az összterületük 60 egység. Így van esély, hogy a 8×8-as táblából 4 mezőt kivágva tényleg le tudjuk fedni a maradékot.

A bizonyítás főbb lépései:

Első ránézésre azt gondolhatnánk, hogy a 2×2-es négyzetet jó sok helyről kivághatjuk. Az ábrán piros ponttal jelöltem a kivágandó négyzetek lehetséges középpontjait:

osszlyuk.png

Néhány lehetséges kivágás:

kivagasok.png

Jobban megfigyelve észrevehetjük, hogy az első és az utolsó ábrán lényegében ugyanaz a helyzet látható, csak elforgatva. Ha tehát az első eset lefedhető, akkor az utolsó is, csak az elemeket is el kell forgatni. A lényegesen különböző esetek a következők:

kulonbozolyukak.png

Ez a 10 eset már nem reménytelenül sok, a türelmes és szorgalmas játékosok nekiállhatnak és megkereshetik a megoldásokat! De Golomb további egyszerűsítéseket alkalmazott a bizonyításban. Ha a V pentominót a lyuk mellé tesszük, akkor egy 3×3-as négyzetet kapunk:

vlyuk.png

Ezt már csak 3 lényegesen különböző helyre tehetjük a sakktáblán:

vlyuktabla.png

Ha ezt a 3 elrendezést sikerül kirakni (a V elem nélkül), akkor az összes elrendezést megoldottuk. Kis kísérletezéssel biztosan sikerülne az olvasónak is, de álljon itt a megoldás:

vlyukmegoldas.png

Így 3 eset vizsgálatával megoldottuk az eredetileg még 49 esetet. Qed.

--------------------------------------------------

A Tetrisből mindenki tudja, hogy 5-féle tetrominó van. Láttuk, hogy 12 pentominó létezik. A blogon is volt már szó a 35 hexominóról. Kapható a 108 heptomino:

heptomino.jpg

Nagyobb készleteket is láttam már, de azok alig-alig játszhatók.

De vajon hány különböző létezik az egyre több négyzetből álló poliominókból? Golomb nem tudta, a könyvének 2. kiadásában a 24-ominók száma szerepel: 654999700403. Akkoriban eddig ismerték az elemszámokat. Azóta sikerült kicsit továbbmenni, ma már a 28-ominók számát is tudjuk: 153511100594603. Mindmáig nem sikerült azonban képletet találni a poliominók pontos számára. Ennek a képletnek vagy minél jobb becslésnek a megtalálása az egyik nagy megoldatlan feladat Golomb könyvéből.

Láttuk a blogon, hogy azonos pentominókból vagy általában poliominókból ki lehet rakni téglalapokat. Ez az egyszerűen megfogalmazható témakör is rejt máig megoldatlan feladványokat. Láttuk, hogy az L pentominóból 2 darabra van szükség a legkisebb téglalap kirakásához, míg az Y-ból már 10-re. Azt is láttuk, az előbb hivatkozott blogbejegyzésben, hogy a viszonylag kicsi, Y alakú  hexominóból is meglepően sok, 92 darab kell a legkisebb téglalaphoz. Van valami módszer, amivel el tudjuk dönteni, hogy egy tetszőleges poliominóból alkotható-e téglalap? És ha igen, akkor hány darab szükséges a legkisebb téglalaphoz? Nem tudjuk. Valószínűleg soha, vagy csak nagyon soká fogunk tudni válaszolni erre a kérdésre. Nagyon nehéz problémának tűnik.

Minden eddig ismert megoldásban páros számú elem kellett a legkisebb téglalap elkészítéséhez. Vajon van-e olyan elem, amiből páratlan sok kell? Nem tudjuk.

Láttuk, hogy az L pentominóból 15 darabbal kirakható téglalap, ami páratlan szám. Vajon minden téglalaposítható poliominóhoz létezik olyan páratlan szám, amennyit felhasználva kirakható belőlük téglalap? Nem tudjuk.

Hogy a páratlan számú elem felhasználásával képezhető problémák nehézségét megérezzük egy kicsit, próbáljon meg az olvasó téglalapot kirakni páratlan sok V triominó felhasználásával:

vtrio.png

 

Számos más érdekes megoldatlan feladvány is található Golomb könyvében. Akiket érdekelnek a nagyon komoly kihívások, azoknak bátran ajánlom őket.

Csak egy szerény példa, hogy mennyire inspirálóan hat Golomb munkássága mind a mai napig. 2 éve az IPP-n az egyik versenyjátékom egy pentominós feladványsorozat volt. Az alábbi 4 pentominó elem közül kettőt, hármat vagy négyet felhasználva kell szimmetrikus alakzatot kirakni:

symptomino.jpg

Tudtommal rajtam kívül még nem vizsgálták a pentominó elemekből kirakható szimmetrikus alakzatokat. Erről majd egy későbbi bejegyzésben részletesen beszámolok.

Golomb nemcsak a játékos matematika területén alkotott maradandót. Munkásságáért megkapta az Egyesült Államok elnöke által adományozott Nemzeti Tudományos Érem kitüntetést is.

Solomon Golomb életének 84. évében ez év május 1-én elhunyt. Ő már nem fog több feladványt és játékot adni nekünk.

Viszlát, és kösz a poliominókat!

Szólj hozzá!

A bejegyzés trackback címe:

http://ordoglakat.blog.hu/api/trackback/id/tr1008863062

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben.

Nincsenek hozzászólások.