A múlt héten befejeződött, kizárólag lányoknak rendezett kijevi matematikai diákolimpián 196 versenyzőből csak 20-an, köztük az aranyérmes, összesítésben 3. helyezett Kerekes Anna tudtak tökéletes megoldást adni az alábbi feladatra. Neked menni fog? (A látszat ellenére ez valójában egy feladat, csak az első változat egy könnyített verzió.)

1.

Vegyünk egy 8x8-as nagyságú, négyzethálós, négyzet alakú táblát. A táblára úgy akarunk néhány dominót lehelyezni, hogy a tábla minden mezőjének pontosan 1 dominóval fedett szomszédja legyen. A tábla két négyzetét szomszédosnak hívjuk, ha nem egyeznek meg, de van közös oldaluk.

A dominó egy 2x1-es vagy 1x2-es téglalap, amiket úgy teszünk le, hogy egymást semelyik négyzeten se fedjék.

Mennyi a legtöbb dominó, ami lerakható a fenti módon a 8x8-as táblára? 

Figyelem, a megoldás két elkülöníthető részből áll: az első rész egy bizonyítás, hogy X-nél biztosan nem lehet több dominót letenni, a másik pedig egy konstrukció, hogy hogyan tennél le X dominót. Bármelyik részre kiváncsiak vagyunk.

2. 

Legyen n bármilyen pozitív egész szám (n=1,2,3 …), és vegyünk egy 2n x 2n nagyságú, négyzet alakú táblát. A táblára úgy akarunk néhány dominót lehelyezni, hogy a tábla minden mezőjének pontosan 1 dominóval fedett szomszédja legyen. A tábla két négyzetét szomszédosnak hívjuk, ha nem egyeznek meg, de van közös oldaluk.

A dominó egy 2x1-es vagy 1x2-es téglalap, amiket úgy teszünk le, hogy egymást semelyik négyzeten se fedjék.

Határozzuk meg n függvényében, minden n-re, hogy hány dominó rakható le legfeljebb a fenti módon a 2n x 2n-es táblára!

Figyelem, a megoldás két elkülöníthető részből áll: az első rész egy bizonyítás, hogy X-nél biztosan nem lehet több dominót letenni, a másik pedig egy konstrukció, hogy hogyan tennél le X dominót. Bármelyik részre kiváncsiak vagyunk.

* * *

Segítség az általános bizonyításhoz:

Színezzük a táblát az alábbi módon fehérre és feketére:

Tekintsük a fekete négyzeteket. Minden egyes négyzetnek, fehérnek és feketének egyaránt, 2 db fekete oldalszomszédja van. Tehát ha leteszünk egy dominót, ami két négyzetet fed le, az pontosan 4 db fekete négyzetnek lesz az oldalszomszédja. Most számoljuk ki, hogy hány fekete négyzet van a 2n x 2n-es táblán, és milyen következtetést tudunk ebből levonni a lehelyezett dominók számáról.

A megoldásokat az eszter.kabos@gmail.com címre várjuk április 21. vasárnap éjfélig. A tökéletes, vagy annak hiányában a legjobb megoldás beküldőjének jutalma Peter Wohlleben sikerkönyve, A fák titkos élete.

A szerző az Oxfordi Egyetem mesterszakos közgazdaságtan-hallgatója. Összes írása a Qubiten itt olvasható.