Problem B. 5310. (April 2023)

B. 5310. A game of strategy is played by four teams on a map represented by an \(\displaystyle n \times n\) square grid (\(\displaystyle n \ge 3\)). Every square field is either sea or land. The bases of the four teams are in the four corners of the map, on land. Given that there is one large connected region of sea on the map and no two bases are connected by a path on land, determine the minimum possible number of fields that represent the sea. (A path consists of adjacent fields. Two fields are adjacent if they have an edge in common. The region of sea is connected in this sense: any two sea squares can be connected by a path consisting of sea squares.)

Proposed by K. Williams, Cambridge

(4 pont)

Deadline expired on May 10, 2023.

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

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\).

Statistics:

101 students sent a solution.
4 points:	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 points:	7 students.
1 point:	58 students.

Problems in Mathematics of KöMaL, April 2023