Feladat: 2005. évi Kürschák matematikaverseny 3. feladata Korcsoport: - Nehézségi fok: -
Füzet: 2006/február, 72 - 73. oldal  PDF file
Témakör(ök): Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2006/február: 2005. évi Kürschák matematikaverseny 3. feladata

2×1-es dominókból tornyot építünk a következő módon. Először elrendezünk 55 dominót úgy, hogy egy 10×11-es téglalapot fedjenek le; ez lesz a torony első szintje. Erre azután további, 55 dominót tartalmazó szinteket építünk, ügyelve arra, hogy minden egyes szint pontosan illeszkedjék az előzőre. Az így kapott építményt akkor nevezzük stabilnak, ha a 10×11-es téglalap minden rácsponttól különböző, belső pontja felett van dominónak belső pontja. Hány szintből áll a legalacsonyabb stabil torony?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Nevezzük a torony által lefedett téglalap 10 hosszú oldalát vízszintesnek, a 11 hosszút pedig függőlegesnek. A toronynak a feladatban leírt tulajdonsága azt jelenti, hogy az említett 10×11 méretű téglalapot (1×1)-es mezőkre osztva bármely két, élben szomszédos mezőhöz van a toronyban olyan dominó, amelyik pontosan e két mező felett található. A függőleges élek mentén szomszédos mezőpárokat nevezzük vízszintes pároknak ‐ 99 ilyen pár van ‐ a vízszintes élek mentén szomszédosakat pedig függőleges pároknak ‐ ezekből 100 darab van.
Először igazoljuk, hogy létezik 5-szintes stabil torony. Világos, hogy két szint elegendő arra, hogy mind a 100 függőleges mezőpárt fedje dominó. A 99 vízszintes párnak a feladatban előírt ,,lefedéséhez'' három újabb szintet használunk fel. A téglalap vízszintes oldala páros, így kiparkettázható olyan dominókkal, amelyek kizárólag vízszintes párokat fednek le. Legyen ez a harmadik szint. Hagyjuk el a téglalap jobb és bal szélső oszlopát, valamint a legfelső sorát! A kapott 8×10-es tábla kiparkettázható csupa vízszintes dominóval. Ez a parkettázás kiterjeszthető az elhagyott szélső mezőkre is, legyen ez a negyedik szint. Mostanra a legfelső sor négy ,,belső'' párját kivéve minden vízszintes párról gondoskodtunk. Egy ötödik szinten ezek is lefedhetők, például az előzőhöz hasonló konstrukcióval, ha most a két szélső oszlopon kívül a legalsó sort hagyjuk el.

 
 

Állítjuk, hogy ha egy torony legfeljebb 4-szintes, akkor nem stabil. Ebből következik, hogy a legalacsonyabb stabil torony éppen 5-szintes. Indirekt módon bizonyítunk. Először is jegyezzük meg, hogy ha egy ilyen torony stabil, akkor legalább 4 szintje van. Valóban: a 10×11-es téglalap minden egyes, nem a szélen fekvő mezejének 4 szomszédja van, és az ezekhez tartozó dominók más-más szinten helyezkednek el. Ha tehát két szomszédos mező valamelyike nem szélső, akkor pontosan egy dominó fedi e két mezőt.
Ha egy m mezőnek 3 élszomszédja van (azaz m a téglalap szélén van, de nem sarokmező), akkor van egy olyan m' élszomszédja, hogy m és m' felett pontosan két dominó van a toronyban, ráadásul, az előbb elmondottak szerint m' szintén szélső mező. Az m mező további 2 élszomszédját pedig egy-egy m-et is fedő dominó fedi. Minthogy tetszőleges élszomszédos mezők között van olyan, amelynek 3 vagy 4 élszomszédja van, a fentiek szerint nincs olyan szomszédos mezőpár, amelyet a toronynak három dominója is fed.
Vizsgáljuk most már azokat a mezőpárokat, amelyeket a toronynak pontosan két dominója fed le! A fentiek szerint ezek a párok diszjunktak, a tábla szélén helyezkedhetnek el, továbbá az egyes sarokmezők mindkét szomszédjukkal ilyen kétszeresen fedett párt alkotnak. A bal alsó sarokmezőben végződő oszlop 11 mezején végighaladva azt találjuk, hogy vagy az oszlopban van olyan mező, amely nem szerepel kétszeresen fedett párban (ez lehetetlen), vagy az oszlop másik végében lévő sarokmező nincs duplán fedve az oszlopszomszédjával, amit szintén kizártunk. Ezzel a bizonyítást befejeztük, négyszintes stabil torony valóban nem létezik.