A B. 5041. feladat (2019. szeptember)

B. 5041. Egy $\displaystyle n \times n$-es táblázat mezőire egy-egy valós számot írunk. Egy ilyen táblázatot nullnégyzetnek hívunk, ha bármely legalább $\displaystyle 2 \times 2$-es négyzet alakú részében (így magában az egész táblázatban is) az elemek összege 0 (az ábrán egy $\displaystyle 3\times3$-as példa látható).

Mekkora a lehető legnagyobb $\displaystyle n$, amelyre van olyan $\displaystyle n \times n$-es nullnégyzet, amelynek nem minden mezőjén 0 áll?

(5 pont)

A beküldési határidő 2019. október 10-én LEJÁRT.

Megoldás. Először megmutatjuk, hogy $\displaystyle n=7$ esetén már nincs nemtriviális nullnégyzet, majd $\displaystyle n=6$ esetén adunk egy nemtriviális kitöltést.

Tekintsünk először egy $\displaystyle 4 \times 4$-es nullnégyzetet, és a mezőiben szereplő számokat jelöljük rendre $\displaystyle a_{1,1}, a_{1,2}, a_{1,3}, a_{1,4}, a_{2,1}, ..., a_{4,4}$-gyel.

Bevezetjük a következő jelölést: az $\displaystyle a_{i,j}$ és az $\displaystyle a_{i+k,j+k}$ sarokmezők által meghatározott nullnégyzetet az $\displaystyle \left(\left( a_{i,j};a_{i+k,j+k} \right) \right)$ módon fogjuk jelölni.
Az $\displaystyle \left(\left( a_{1,1};a_{3,3} \right) \right)$ $\displaystyle 3 \times 3$-as nullnégyzetnek az $\displaystyle a_{2,2}, a_{2,3}, a_{3,2}, a_{3,3}$ mezők által meghatározott $\displaystyle 2 \times 2$-es nullnégyzet a része, emiatt a kimaradó 5 elem összege 0, azaz $\displaystyle a_{1,1}+a_{1,2}+a_{1,3}+a_{2,1}+a_{3,1} = 0$.
Hasonlóan az $\displaystyle \left(\left( a_{2,2};a_{4,4} \right) \right)$ $\displaystyle 3 \times 3$-as nullnégyzetnek is része az $\displaystyle a_{2,2}, a_{2,3}, a_{3,2}, a_{3,3}$ mezők által meghatározott $\displaystyle 2 \times 2$-es nullnégyzet, azaz $\displaystyle a_{4,2}+a_{4,3}+a_{4,4}+a_{2,4}+a_{3,4} = 0$.
Másfelől mivel a kiinduló $\displaystyle 4 \times 4$-es nullnégyzetünkben is 0 az elemek összege és az ebben a négyzetben szereplő számok pontosan a középső $\displaystyle 2\times2$-es nullnégyzet, a két "oldalt kimaradó" 5-5 nulla összegű elem, illetve $\displaystyle a_{1,4}$ és $\displaystyle a_{4,1}$, ezért $\displaystyle a_{4,1} + a_{1,4} = 0$. Innen nyilvánvalóan következik, hogy egy legalább négy méretű nullnégyzetben az egymástól átlósan három távolságra lévő mezőpárok esetén ezen mezők számainak összege 0; azaz $\displaystyle a_{i,j}+a_{i+3,j+3}=0$, illetve $\displaystyle a_{i,j}+a_{i+3,j-3}=0$.
Nagyobb $\displaystyle (k+1) \times (k+1)$-es ($\displaystyle k>3$) nullnégyzetből kiindulva pontosan ugyanígy megmutatható, hogy az egymástól átlósan $\displaystyle k$ távolságra lévő mezőpárok esetén ezen mezők számainak összege is 0; azaz $\displaystyle a_{i,j}+a_{i+k,j+k}=0$, illetve $\displaystyle a_{i,j}+a_{i+k,j-k}=0$.

Ezek után vizsgáljunk egy $\displaystyle 5 \times 5$ méretű nullnégyzetet (a mezőket $\displaystyle a_{1,1}$-től $\displaystyle a_{5,5}$-ig jelöljük).
Az $\displaystyle \left(\left( a_{3,3};a_{5,5} \right) \right)$, valamint az $\displaystyle \left(\left( a_{4,4};a_{5,5} \right) \right)$ nullnégyzet volta miatt (az előzőekhez hasonlóan) a kimaradó 5 elem összegére: $\displaystyle a_{3,3}+a_{3,4}+a_{3,5}+a_{4,3}+a_{5,3}=0$.
Másfelől a teljes $\displaystyle 5 \times 5$-ös nullnégyzetünk előáll az $\displaystyle \left(\left( a_{1,1};a_{3,3} \right) \right)$, az $\displaystyle \left(\left( a_{1,4};a_{2,5} \right) \right)$, a $\displaystyle \left(\left( a_{4,1};a_{5,2} \right) \right)$ és a $\displaystyle \left(\left( a_{4,4};a_{5,5} \right) \right)$ nullnégyzetek, valamint a négy kimaradó $\displaystyle a_{3,4}, a_{3,5}, a_{4,3}, a_{5,3}$ mezők diszkrét uniójaként. Emiatt $\displaystyle a_{3,4}+a_{3,5}+a_{4,3}+a_{5,3}=0$ és így $\displaystyle a_{3,3}=0$, azaz egy $\displaystyle 5 \times 5$-ös nullnégyzet középső mezőjén csak 0 állhat.

Most már térjünk rá a $\displaystyle 7 \times 7$-es eset tárgyalására!
A $\displaystyle 7\times 7$-es nullnégyzet középső $\displaystyle \left(\left( a_{3,3};a_{5,5} \right) \right)$ 9 mezője közül valamennyi egy megfelelő $\displaystyle 5 \times 5$ méretű nullnégyzet középső mezője, azaz mindegyik helyen 0 áll.
Ezért a tőlük átlósan 3-ra lévő mezőkön is csak 0 állhat az $\displaystyle a_{i,j}+a_{i+3,j+3}=0$, illetve $\displaystyle a_{i,j}+a_{i+3,j-3}=0$ szabályok miatt; azaz a nagy nullnégyzet $\displaystyle \left(\left( a_{1,1};a_{2,2} \right) \right)$-es, $\displaystyle \left(\left( a_{6,1};a_{7,2} \right) \right)$ -es, $\displaystyle \left(\left( a_{1,6};a_{2,7} \right) \right)$-es és $\displaystyle \left(\left( a_{6,6};a_{7,7} \right) \right)$-es részeiben szintén minden szám 0.
Innen $\displaystyle a_{2,3}=a_{3,2}=a_{5,2}=a_{6,3}=a_{3,6}=a_{5,2}=a_{5,6}=a_{6,5}=0$, mert minden ilyen mező átlósan négy távolságra van az imént vizsgált $\displaystyle 2\times2$ méretű csupa 0 számot tartalmazó nullnégyzet egy-egy mezőjétől. (Például az $\displaystyle a_{1,2}=0$ mezőtől négy távol van az $\displaystyle a_{1+4,2+4} = a_{5,6}$ mező).
A még nem tárgyalt mezők esetén pedig rendre mindegyik mezőhöz van olyan $\displaystyle 2 \times 2$-es méretű nullnégyzet, amelynek három már ismert eleme mind 0, azaz a kimaradó mezők is mind 0-k.

Vagyis nincs nemtriviális $\displaystyle 7\times7$ méretű nullnégyzet.

A leírt bizonyítás lépéseit szemlélteti az alábbi ábra:

$\displaystyle n=6$ esetre pedig adható példa:

Azaz legfelejebb $\displaystyle 6 \times6$-os méretben létezik nemtriviális nullnégyzet.

Statisztika:

85 dolgozat érkezett.
5 pontot kapott:	58 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	13 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	2 dolgozat.

A KöMaL 2019. szeptemberi matematika feladatai