Ördöglakat

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

Friss topikok

Parttalan pentominók

2011.01.22. 17:16 Gál Péter F.

Képzeljük el, egy szigetet, melyen pentominó alakú országok helyezkednek el!. Egy régebbi cikkben már foglalkoztunk pentominó-téglalapokkal, az egyszerűség kedvéért eleinte most is  az ilyen alakú szigeteket vizsgáljuk, de egy másik szempontból. Tudomásom szerint még senki nem foglalkozott a következőkben ismertetett problémakörrel ilyen részletességgel.

Tekintsük az első szigetet:

Láthatjuk, hogy 3 pentominó „ország” nem érintkezik a kék „tengerrel”, ezek a W, a T és az X. A tengerrel nem érintkező elemeket hívhatjuk parttalanoknak.

Vajon létezik-e ugyanennek a téglalapnak olyan kirakása, amiben csak 2 parttalan elem található? A válasz pozitív, ahogy a következő ábrán is látható:

Itt az Y és az N nem érintkezik a tengerrel.

Van olyan elrendezés is, amelyben csak egy elem, pl. az F parttalan:


Sőt olyan is, ahol minden ország tengerrel határos:

 

De mennyi lehet ebben a téglalapban a parttalan elemek maximális száma? A kérdést egyáltalán nem egyszerű megválaszolni, muszáj volt számítógépes segítséget igénybe vennem. Azt találtam, hogy legfeljebb 4 ilyen elem létezhet és mindössze 13 olyan elrendezés van, ahol ez a maximum előfordul. Ezek közül látható egy a következő képen:

Az eddig szereplő esetek mindegyike több megoldással is rendelkezik. Próbáljon az olvasó másikakat találni! Talán a legnehezebb feladat megtalálni azt az elrendezést, amelyben az I elem is parttalan, mindössze egy ilyen létezik.

Kevésbé bonyolult a helyzet a 4x15-ös téglalap esetén. Lehet minden ország tengerrel határos:

És lehet egy elem parttalan. Pl az N:

Nagyon nehéz olyan elrendezést találni, ahol más elem parttalan! Próbálkozzon vele az olvasó!

Ebben a téglalapban nem is lehetséges 2 vagy több parttalan elemet kialakítani.

A 6x10-es téglalap elég „vastag” ahhoz, hogy jó sok parttalan elem lehessen benne. Meglepő módon itt is csak maximum 4 lehet. Íme, az egyike a 200-nál is több megoldásnak:

 

Sokkal nehezebb olyan elrendezést találni, ahol minden országnak van tengere. Mindössze 2 ilyen létezik, ez az egyik:

Sikerül megtalálni a másikat? (Rendkívül nehéz!)

Az 1, 2 illetve 3 parttalan elemet tartalmazó elrendezéseket az olvasóra bízom. Talán a legnehezebb megtalálni azt, ahol egyedül a V nem érintkezik a tengerrel.

A fentieken kívül még egy téglalap rakható ki pentominókból, ez pedig a 3x20-as, a maga mindössze két megoldásával. Ezek közül egyik sem tartalmaz parttalan elemet.

Nagyon kíváncsi vagyok, hogy más alakú szigetek esetén maximálisan hány parttalan elem létezhet. Azt gondolom, hogy minél „tömörebb” egy alakzat, annál több lehetőség van elemek elzárására. Megvizsgáltam néhány 8x8-as elrendezést is. (Az ilyenekről szólt a sakktáblás bejegyzés.)

Hamar sikerült is 5 elzárt elemet találni. Például a négy sarkán csonkolt sakktáblán:

Vagy amikor a sakktábla sarkából egy nagyobb négyzetet vágunk ki:

De itt megakadtam. Jelenleg nem tudok olyan alakzatot, amiben 6 vagy több parttalan elem található.

Hátha az olvasónak sikerül találni!

3 komment

Címkék: 2d összerakó kombinatorikus összerakó kirakó megoldatlan probléma put together pentomino pentamino

A bejegyzés trackback címe:

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

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.

mimindannyian · http://wmiki.blog.hu/ 2011.01.23. 17:34:12

Jellegzetesen olyan nem lineáris feladat, amelyre csak a brute force keresés működik, viszont a kombinatorikai robbanás ezt nehézzé teszi.

Gál Péter F. · http://ordoglakat.blog.hu/ 2011.01.23. 17:49:28

@mimindannyian: Hát. igen. Ilyenkor kellenek az ötletek, sejtések. Amikor már nem elég a nyers erő.

treedog 2011.01.31. 03:46:37

az első kérdés megválaszolása nem csak megbonyolítja a megoldást? én lusta vagyok, ezért a téglalap jobboldaláról leválasztható négyzet alakú összerakott lapot elfordítottam 90 fokkal, az elég volt, papírvagdosás nélkül ennyire tellett :)