A B. 5310. feladat (2023. április)

B. 5310. Egy stratégiai játékot négy csapat játszik egy \(\displaystyle n \times n\)-es négyzetrácsra rajzolt térképen (\(\displaystyle n \ge 3\)). Minden négyzet alakú mező víz vagy szárazföld. A négy csapat bázisa a térkép négy sarkában, szárazföldön van. Tudjuk, hogy a térképen egyetlen nagy, összefüggő vízfelület van, és hogy semelyik két bázis között nem vezet út végig szárazföldön haladva. Legalább hány mezőt foglal el víz? (Egy út során akkor léphetünk egyik mezőről a másikra, ha közös élen találkoznak. A vízfelület olyan értelemben összefüggő, hogy bármely mezőjéről bármelyikre vezet ilyen út csak vizes mezőkön keresztül.)

Javasolta: Williams Kada (Cambridge)

(4 pont)

A beküldési határidő 2023. május 10-én LEJÁRT.

Megoldás. Azt igazoljuk, hogy a válasz \(\displaystyle 2n-1\). Ha a második sorban és a második oszlopban lévő mezők mindegyike víz, akkor a feltételek teljesülnek, és ez összesen \(\displaystyle 2n-1\) mező. A továbbiakban megmutatjuk, hogy ennél kevesebb víz mező nem elég.

A sorokat, illetve oszlopokat számozzuk meg 1-től \(\displaystyle n\)-ig fentről lefelé, illetve balról jobbra. A bal felső sarokból az 1. oszlopon végighaladva nem lehet elsétálni a bal alsó sarokba végig szárazföldön haladva, így az 1. oszlopban biztosan van víz mező, ezek egyike legyen az \(\displaystyle A\) mező. Ehhez hasonlóan az utolsó oszlopban, az első sorban és az utolsó sorban is van víz mező, például legyenek ezek rendre \(\displaystyle B\), \(\displaystyle C\) és \(\displaystyle D\).

A vízfelület összefüggő, így \(\displaystyle A\)-ból \(\displaystyle B\)-be el lehet jutni végig víz mezőkön haladva. Tegyük meg ezt az utat úgy, hogy semelyik mezőre nem lépünk 1-nél többször. Az utunk során érintett mezők között a(z egyik) legmagasabban (legkisebb indexű sorban) lévő legyen \(\displaystyle E\), a(z egyik) legalacsonyabban (legnagyobb indexű sorban) lévő pedig legyen \(\displaystyle F\). Tegyük fel, hogy \(\displaystyle E\) az \(\displaystyle i\)-edik sorban, \(\displaystyle F\) pedig a \(\displaystyle j\)-edik sorban van, ekkor \(\displaystyle 1\leq i\leq j\leq n\). Mialatt \(\displaystyle A\)-ból \(\displaystyle B\)-be eljutottunk, legalább \(\displaystyle (n-1)\)-szer léptünk jobbra, és fel-le lépésből is volt legalább \(\displaystyle j-i\) (már az \(\displaystyle E\) és \(\displaystyle F\) közötti útszakaszon is). Ez összesen legalább \(\displaystyle n-1+j-i=n-i+j-1\) lépés, vagyis az út során legalább \(\displaystyle n-i+j\) víz mezőt érintettünk. \(\displaystyle E\) és \(\displaystyle F\) definíciója alapján ezek egyike sincs az \(\displaystyle 1,2,\dots,i-1,j+1,j+2,\dots,n \) indexű sorokban. Mivel \(\displaystyle C\) az első, \(\displaystyle D\) pedig az \(\displaystyle n\)-edik sorban lévő víz mező, a vízfelület pedig összefüggő, ezért minden sorban van legalább egy víz mező (hiszen \(\displaystyle C\)-ből víz mezőkön haladva eljuthatunk \(\displaystyle D\)-be). Így az \(\displaystyle A\) és \(\displaystyle B\) közötti utunk során érintett \(\displaystyle n-i+j\) víz mező mellett az \(\displaystyle 1,2,\dots,i-1,j+1,j+2,\dots,n \) indexű sorokban található víz mezőkkel együtt legalább \(\displaystyle (n-i+j)+(i-1)+(n-j)=2n-1\) víz mezőnek kell lennie.

Tehát a feladat kérdésére a válasz: \(\displaystyle 2n-1\).

Statisztika:

101 dolgozat érkezett.
4 pontot kapott:	Ali Richárd, Aravin Peter, Bodor Mátyás, Chrobák Gergő, Csupor Albert Dezső, Czanik Pál, Czirják Márton Pál, Diaconescu Tashi, Domján Olivér, Fajszi Karsa, Fórizs Emma, Görömbey Tamás, Holló Martin, Horváth 530 Mihály, Juhász-Molnár Erik, Keresztély Zsófia, Kocsis 827 Péter, Kovács Benedek Noel, Makrai Norbert, Melján Dávid Gergő, Mizik Lóránt, Nádor Artúr, Nguyen Kim Dorka, Op Den Kelder Ábel, Prohászka Bulcsú, Sági Mihály, Sárdinecz Dóra, Szakács Ábel, Szakács Domonkos, Szalontai Júlia, Tarján Bernát, Teveli Jakab, Tran Dávid, Varga Boldizsár, Zhai Yu Fan.
2 pontot kapott:	7 versenyző.
1 pontot kapott:	58 versenyző.

A KöMaL 2023. áprilisi matematika feladatai