Ördöglakat

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

Friss topikok

  • Gál Péter F.: @ClownPepito: Felváltva kell lépni, és az veszt, aki már nem tud? Mondjuk, ez lehet egy 2 személye... (2018.06.05. 14:52) Szoliter – Háromszög tábla, kevés bábu
  • Gál Péter F.: @Könyveslány: Köszi, igyekszem. (2018.05.01. 11:20) Fémépítő ördöglakat
  • Gál Péter F.: @bbalint85: Ezekhez az elemzésekhez saját programokat használok. Létezik a BurrTools nevű remek me... (2018.03.04. 22:06) Hasábok félkockákból
  • Gál Péter F.: @Steve Rush: Tisztelt Steve! Nagyon örülök, hogy a matekórákra is betörnek az ördöglakatok! Szív... (2018.01.13. 20:53) Tangram készlet
  • gigabursch: Azt hittem, hogy kipörgetős az ördöglakat, de nem... (2017.09.04. 12:24) Borotvák

Pentominó a sakktáblán

2009.11.09. 20:33 Gál Péter F.

A 12 pentominó elemből (lásd itt) nem lehet négyzet formában elrendezni, hisz összesen 60 négyzetből állnak. A 60-hoz legközelebbi négyzetszám a 64, így felmerül a kérdés, hogy vajon egy 8-szor 8-as négyzetben elhelyezhetők-e az elemek, úgy hogy pár mezőt üresen hagyunk. A válasz igenlő, mint a képen is látható:

Egyáltalán nem egyszerű feladat ez! Kisebb gyerekeknek vagy a játékkal csak most ismerkedőknek már az is jó eredmény, ha 10-11 elemet el tudnak helyezni a négyzet belsejében! A gyakorlott játékosoknak pár (tíz) perc türelemmel és próbálgatással biztosan sikerül az összes elemet felrakni a "sakktáblára". Akiknek ez már könnyen megy, próbálkozhatnak kikötéseket tenni a lyukak elhelyezkedésére.

Például: alkosson a 4 lyuk is egy négyzetet! Lehetséges ez? Esetleg a négyzet alakú lyuk lehet a tábla közepén is? A válasz ismét igen:

Érdekes, hogy ez a feladvány már jóval a pentominó szó megalkotása előtt megjelent. 1907-ben adta ki Henry Dudeney a Canterbury puzzles című rejtvénygyűjteményét, és már ebben szerepelt a sakktábla hasonló felosztása. Mint minden feladványához, Dudeney ehhez is egy jópofa történetet eszelt ki, így nem volt szüksége az elemek elnevezésére.

De vajon egynél több kirakás is létezik? Hány megoldása lehet a feladatnak?  Ezekre a kérdésre már sokkal nehezebb a válasz. A teljes elemzésig 1958-ig kellett várni. Ekkor számítógépes elemzéssel kimutatták, hogy 65 lényegesen különböző megoldás létezik. (Mennyivel meglepőbb lett volna, ha 64! De sajnos nem, nincs újabb adu a számmisztika híveinek kezében.) A programot Dana Scott készítette és ez volt az egyik első alkalmazása a backtrack algoritmusnak.

Hol lehet még a 2*2-es négyzet alakú lyuk? Lehet a tábla sarkában? Vagy valamelyik oldal közepén? A teljesen pontos válasz több programozó és játékos együttes munkájának köszönhető. Ma már tudjuk, hogy akárhova is helyezzük a 2*2-es lyukat, a fennmaradó rész lefedhető pentominó elemekkel.

Például lyuk a sarokban:

 Megkívánhatjuk, hogy a négy lyuk ne legyen egy "kupacban" viszont alkossanak valamilyen szép, szimmetrikus elrendezést. Pl. ilyet:

 

Vagy legyen a tábla négy sarkában a négy lyuk! Vagy a négy lyuk elhelyezése legyen forgásszimmetrikus, de ne legyen tengelyesen szimmetrikus:

 

Vagy épp fordítva, tengelyesen szimmetrikus, de nem forgásszimmetrikus:

Egyáltalán van bármi megkötés a lyukak lehetséges elhelyezésére? Akárhol lehet a 4 lyuk?

Sok-sok irodalmat olvastam a témában, mindenhol az szerepelt, hogy a négy lyuk tetszőlegesen elhelyezhető, a maradék tábla lefedhető. Kis töprengés után rájöttem, hogy ez nyílván nem igaz, hisz ha lyukakkal elkerítünk valamelyik sarokban egy vagy két mezőt, akkor nyílván nem lesz lefedhető a tábla. De mi van azokban az esetekben, amikor nincs elkerítés, a tábla összefüggő marad? Azt hiszem, erre először én találtam meg a választ. Van két eset, amikor a tábla összefüggő és mégsem lefedhető. Így utólag már egyszerűnek tűnik a probléma, de amikor megtaláltam (számítógéppel) a megoldásokat, az komoly AHA élmény volt. De most már segítettem egy kicsit. Megtalálja az olvasó is?

Összegzésül:

Két lényegesen különböző kivételtől eltekintve minden 4 lyukú, összefüggő sakktábla lefedhető pentominó elemekkel. Ez több ezer lehetséges elrendezés. Ha valaki kézzel akarja az összeset megoldani, hamar el kell kezdenie!

Van néhány nem összefüggő elrendezés is, ami megoldható. Talál ilyet az olvasó?

A képeken az új pentominó készletem szerepel. Most lettem kész vele, nagyon örülök neki, szerintem jól sikerült. Mondjuk, hogy ez az útravaló készlet. Kis könyvecske, zsebre tehető, bárhol elő lehet venni, nem is esnek ki belőle az elemek. Csak a könyv részét készítettem én, az elemek lézerrel vannak kivágva. A könyvecske becsukva, és a tartógumival rögzítve:

7 komment

Címkék: pakolás 2d összerakó kombinatorikus put together pentomino pentamino

A bejegyzés trackback címe:

https://ordoglakat.blog.hu/api/trackback/id/tr21513706

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 és az adatvédelmi tájékoztatóban.

bigyibogyo 2009.11.09. 22:54:00

ez akkor szivas ha kezdo vagy es gyorsan akarod elrakni ;)
amugy hol lehet ilyet venni?

Gál Péter F. · http://ordoglakat.blog.hu/ 2009.11.10. 10:44:37

@bigyibogyo:

Igen, ez nem a gyors játékok kedvelőinek való!

Ilyet biztos, hogy sehol nem lehet venni. Ezt én készítettem és készíttettem.

Hasonlót talán jobb játékboltokban lehet találni. De az eladók sem szokták tudni, hogy mi is az :)

gelsystem 2010.11.28. 19:39:16

fasza!!!!!!!!!!!!!!!!
nekem volt egy ilyenem papírból 8*8 sakktáblára -fekete/fehér- festve.....
szétszedtem, sosem sikerült összeraknom:(
és, ha jól emléxem, BIZTOS hogy telibe volt, nem voltak benne lyukak......!
sajna, már elveszett:(:(
ha valaki tud esetleg, dobjon bitpostát:)!

Gál Péter F. · http://ordoglakat.blog.hu/ 2010.11.28. 19:48:48

@gelsystem:
Láttam már ilyesmit úgy árulni, hogy volt az elemek között egy 2*2-es négyzet is. Vagyis a második képen látható elrendezésben a lyuk helyett is volt egy elem.

gelsystem 2010.11.28. 20:21:31

@Gál Péter F.:
AZAAAAAAAAAAAAAAAAZ:):):)
hol??????

gelsystem 2010.11.28. 20:22:49

@gelsystem:
bááááár, hegesztek egyet:):):):)
legalább az alkotás élménye is meglesz...............:)