Problem B. 5052. (October 2019)

B. 5052. Two players, First and Second take turns in writing a number 0 or 1 in the fields of a \(\displaystyle 19\times 19\) table, initially all blank. When all fields are filled in, they calculate the sum of each row, and the sum of each column. Let the largest row sum be \(\displaystyle A\), and let the largest column sum be \(\displaystyle B\). If \(\displaystyle A>B\) then First wins the game. Second wins if \(\displaystyle A<B\), and it is a draw if \(\displaystyle A=B\). Does either of the players have a winning strategy?

(6 pont)

Deadline expired on November 11, 2019.

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

Megoldás. Először megmutatjuk, hogy Második el tudja érni, hogy ne veszítsen. Mutatunk egy olyan stratégiát, amivel el tudja érni, hogy minden sorösszeg értéke 9 vagy 10 legyen, majd megmutatjuk, hogy ez garantálja számára a legalább döntetlen eredményt.

Második célja az lesz, hogy a játék során végig, miután ő következett, az összes sor ,,kiegyensúlyozott'' legyen, abban az értelemben, hogy az összes sorban a már kitöltött mezők közül a 0-t és 1-et tartalmazók számának különbsége legfeljebb 1 legyen. (Tehát páros sok kitöltött mező esetén a mezők fele 0-t, fele 1-et tartalmaz, páratlan sok kitöltött mező esetén valamelyik értékből pontosan 1-gyel több van.)

Ennek eléréséhez a következő stratégiát követi:

• [(i)] Ha Kezdő legutolsó lépése egy olyan sorban volt, ahol még ezután is maradt kitöltetlen mező, akkor Második ugyanebben a sorban tölt ki egy mezőt, ahova éppen ellentétes értéket ír Kezdő választásához képest.
• [(ii)] Ha Kezdő egy sort ,,befejezett'' (lépése után ott már nincs kitöltetlen mező), akkor Második választ a többi sor közül egy olyat, amiben még van kitöltetlen mező, és ebbe olyan értéket ír, hogy kiegyensúlyozott legyen a sor a lépés után is. (Ha páratlan sok kitöltött érték van eddig, akkor azt, amelyik 1-gyel kevesebbszer szerepel, ha páros sok, akkor tetszőleges módon választ.)

Megmutatjuk, hogy ez a stratégia garantálja, hogy Második lépése után mindig minden sor kiegyensúlyozott. A játék legelején (Kezdő első lépése előtt) ez természetesen fennáll.

Tekintsük a játék során Kezdő egy tetszőleges lépését. Ha ezzel nem fejezett be sort, akkor (i) alapján Második ugyanabba a sorba ír, ellentétes értéket, így mivel Kezdő lépése előtt minden sor kiegyensúlyozott volt, így Második mostani lépése után is az lesz.

Ha Kezdő befejezett egy sort, akkor abban a sorban végül éppen 1-gyel többször szerepel az az érték, amit Kezdő utoljára beírt, hiszen ezt megelőzően a kitöltött 18 érték közül 9-nek 0-nak, 9-nek 1-nek kellett lennie. Tehát a Kezdő által befejezett sor kiegyensúlyozott lett. Második (ii) alapján választ egy sort, aminek kiegyensúlyozottságát (ii) szerint eljárva nem rontja el, így Második lépése után továbbra is minden sor kiegyensúlyozott.

Tehát a stratégiát követve Második eléri, hogy lépése után mindig minden sor kiegyensúlyozott. Bár a játék Kezdő lépésével ér véget (hiszen \(\displaystyle 19^2\) páratlan), mivel a legutolsó lépés előtt minden sor kiegyensúlyozott volt, ezért Kezdő utolsó lépése után is az marad.

Tehát a játék végén minden sorban 9 vagy 10 lesz az összes sorösszeg.

Ha a sorösszeg minden sorban 9, akkor \(\displaystyle A=9\), és az oszlopösszegek összege is éppen \(\displaystyle 19\cdot 9\) (ahogy a sorösszegeké), így a legnagyobb oszlopösszeg nem lehet 9-nél kisebb: \(\displaystyle B\geq 9\). Ha van 10-es sorösszeg, akkor \(\displaystyle A=10\), és az oszlopösszegek összege több, mint \(\displaystyle 19\cdot 9\), vagyis lesz 9-nél nagyobb oszlopösszeg, és így \(\displaystyle B\geq 10\). Azt kaptuk tehát, hogy mindenképpen \(\displaystyle B\geq A\), vagyis Második számára garantált a legalább döntetlen eredmény.

Kezdő stratégiája ehhez teljesen hasonló, csak a sorok és oszlopok szerepét kell felcserélni (és így végül azt tudja garantálni, hogy minden oszlopösszeg 9 vagy 10 legyen). A fent ismertetett stratégiában Kezdő és Második szerepét felcserélve, valamint ,,sor'' helyett mindig ,,oszlopot'' véve kapjuk Kezdő stratégiáját. Kezdéskor - ahhoz hasonlóan, mintha Második egy lépésével egy oszlop utolsó mezőjét töltötte volna ki - Kezdő egy tetszőlegesen választott mezőbe ír 0-t, vagy 1-et. Innentől a fenti stratégiát követi, és a fenti indoklás mutatja (a sorok és oszlopok szerepét megcserélve), hogy Kezdő minden lépése után az összes oszlop kiegyensúlyozott. Így a játék végén vagy \(\displaystyle B=9\leq A\) vagy \(\displaystyle B=10\leq A\) lesz, vagyis mindkét esetben garantált Kezdő számára a legalább döntetlen eredmény.

Tehát egyiküknek sincsen nyerő stratégiája.

Statistics:

58 students sent a solution.
6 points:	Argay Zsolt, Asztalos Ádám, Bán-Szabó Áron, Beke Csongor, Bukva Dávid, Csizmadia Miklós, Czett Mátyás, Fekete Richárd, Fleiner Zsigmond, Fülöp Csilla, Füredi Erik Benjámin, Hámori Janka, Jánosik Máté, Kercsó-Molnár Anita, Kovács 129 Tamás, Kun Ágoston , Lengyel Ádám, Mezey Dorottya, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Nagy Nándor, Németh Norbert Marcell, Sebestyén Pál Botond, Szabó 991 Kornél, Szakács Ábel, Terjék András József, Velich Nóra, Világi Áron.
5 points:	Fey Dávid, Hervay Bence, Kitschner Bernadett, Kocsis Anett, Nagy 551 Levente, Németh Márton, Rareș Polenciuc, Tiderenczl Dániel.
4 points:	5 students.
3 points:	1 student.
2 points:	8 students.
0 point:	7 students.

Problems in Mathematics of KöMaL, October 2019