Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5052. feladat (2019. október)

B. 5052. Kezdő és Második egy kezdetben üres \(\displaystyle 19\times 19\)-es táblázat mezőibe ír felváltva egy-egy számot, 0-t vagy 1-et. Amikor már az összes mező ki van töltve, kiszámolják a sorösszegeket és az oszlopösszegeket. A legnagyobb sorösszeg legyen \(\displaystyle A\), a legnagyobb oszlopösszeg pedig \(\displaystyle B\). Ha \(\displaystyle A>B\), akkor Kezdő nyer; ha \(\displaystyle A<B\), akkor Második; ha pedig \(\displaystyle A=B\), akkor döntetlen a játék eredménye. Van-e valakinek nyerő stratégiája?

(6 pont)

A beküldési határidő 2019. november 11-én LEJÁRT.


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.


Statisztika:

A B. 5052. feladat értékelése még nem fejeződött be.


A KöMaL 2019. októberi matematika feladatai