Problem B. 5424. (December 2024)

B. 5424. For an arbitrary positive integer \(\displaystyle n\) let \(\displaystyle K_n\) denote the shape obtained by cutting out an \(\displaystyle {(n-1)\times (n-1)}\) square from all four corners of a \(\displaystyle (2n)\times (2n)\) `chessboard' according to the diagrams.

Let \(\displaystyle a_n\) denote the number of ways \(\displaystyle K_n\) can be partitioned into \(\displaystyle 1\times 2\) `dominoes' (for example, \(\displaystyle a_1=2\) and \(\displaystyle a_2=8\)). Prove that \(\displaystyle 2a_n\) is a perfect square for every \(\displaystyle n\).

Proposed by: Attila Sztranyák, Budapest

(4 pont)

Deadline expired on January 10, 2025.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. \(\displaystyle K_1\) lefedéseinek a száma 2 (ennek duplája valóban négyzetszám); a továbbiakban foglalkozzunk az ettől ,,nagyobb'' \(\displaystyle K_n\)-ekkel. A könnyebb leírás érdekében tájoljuk az alakzatunkat az égtájok szerint, majd vizsgáljuk a tábla középső \(\displaystyle 2 \times 2\)-es négyzetét. Ennek (az alábbi ábrán ,,sraffozottan'' megjelölt) jobb felső mezőjét nyilván le kell fedni valahogyan, vagy egy függőleges, vagy egy vízszintes dominóval. Tegyük fel, hogy (mint az ábrán) egy függőleges dominóval fedjük le.

Ekkor két lehetőség van;

– Ha a lefedő dominó a jelölt mezőt és a tőle délre lévő mezőt fedi le (középső ábra), akkor a jelölt mezőtől észak-nyugatra lévő, pirossal jelölt mező nem fedhető le olyan függőleges dominóval, aminek a piros mező az északi mezeje, mert ekkor az alakzat ,,északi'' ágában lévő lefedetlen maradéka páratlan mezőt tartalmazna. Hasonló okokból a középső ábra másik pirossal jelölt mezője sem fedhető le olyan függőleges dominóval, aminek a piros mező a déli mezeje. Ekkor (középső) ábránkon dominószélekből kialakul az ábrán kékkel megrajzolt (elforgatott) H betű.

– Ha pedig a lefedő dominó a jelölt mezőt és a tőle északra lévő mezőt fedi le (jobb oldali ábra), akkor a jelölt mezőtől észak-nyugatra lévő, pirossal jelölt mező csak olyan függőleges dominóval fedhető le, amelynek ez a piros mező az északi mezeje (különben az ,,északi ág maradéka'' megint csak páratlan mezőt tartalmazna); továbbá az előzőekhez hasonlóan az ábrán lévő két további piros mező sem fedhető le olyan dominókkal, aminek a másik mezeje a tábla középső \(\displaystyle 2\times 2\)-es négyzetének valamelyik mezeje. Így ebben az esetben (jobb oldali ábra) is kialakul az iménti, kékkel megrajzolt H betű (csak ,,állva'').

Nyilván ha a jelölt mezőt lefedő dominó vízszintes, akkor is ugyanez a helyzet; azaz az alakzatunk középpontja egyúttal középpontja egy dominószélekből álló \(\displaystyle 2 \times 2\)-es méretű H betűnek is, továbbá a H betű kétféleképpen állhat (,,állva'', vagy ,,elforgatva'').

Ez a H betű kettévágja az alakzatunkat 2 darab \(\displaystyle 2 \times (n-1)\)-es és 2 darab \(\displaystyle 2 \times n\)-es részre, amelyek egymástól függetlenül parkettázhatók. Jelöljük \(\displaystyle g_n\)-nel egy \(\displaystyle 2 \times n\)-es téglalap dominólefedéseinek a számát. Ekkor a fentiek szerint az alakzatunk lefedéseinek a száma \(\displaystyle a_n = 2 \cdot g^2_n \cdot g^2_{n-1} = 2 \left( g_n \cdot g_{n-1} \right)^2\), aminek kétszerese valóban egy négyzetszám.

Megjegyzés: Viszonylag ismert, hogy a \(\displaystyle 2 \times n\)-es téglalap dominólefedéseinek a száma \(\displaystyle g_n=f_{n+1}\) (az \(\displaystyle (n+1)\)-dik Fibonacci szám). Ebből \(\displaystyle K_n\) alakzat lefedéseinek a száma \(\displaystyle a_n= 2 \cdot f^2_{n+1} \cdot f^2_{n}\).

Statistics:

83 students sent a solution.
4 points:	Ali Richárd, Aravin Peter, Balla Ignác , Baran Júlia, Beinschroth Máté, Bencze Mátyás, Bodor Ádám, Bogdán Balázs Ákos, Bolla Donát Andor, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Czanik Dániel, Dancs Bálint, Fodor Barna, Görömbey Tamás, Gyenes Károly, Hajba Milán, Hajszter Dóra, Hideg János, Hodossy Réka, Holló Martin, Horák Zsófia, Juhász Emma, Kovács Benedek Noel, Li Mingdao, Ligeti Ábel, Miszori Gergő, Molnár István Ádám, Pázmándi József Áron, Péter Hanna, Prohászka Bulcsú, Sajter Klaus, Sánta Gergely Péter, Sárdinecz Dóra, Szabó 721 Sámuel, Tamás Gellért, Tulkán Dávid, Varga 511 Vivien, Virág Lénárd Dániel, Virág Tóbiás, Vödrös Dániel László, Wágner Márton, Wiener Marcell, Zhai Yu Fan.
3 points:	20 students.
2 points:	2 students.
1 point:	3 students.
0 point:	12 students.

Problems in Mathematics of KöMaL, December 2024