Feladat: B.5052 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Czett Mátyás 
Füzet: 2020/október, 413 - 414. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Többszemélyes véges játékok, Logikai feladatok
Hivatkozás(ok):Feladatok: 2019/október: B.5052

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megmutatjuk, hogy Kezdő számára létezik nem vesztő stratégia.
Legyen Kezdő első száma 0, mindegy, hogy hol. Ezt követően Kezdő minden további lépésében a Második által előtte beírt számtól különböző számot ír be: ha van hely abban az oszlopban, ahová Második utoljára írt számot, akkor abba az oszlopba, különben pedig egy olyan oszlopba, amibe hasonló esetben még nem tett számot. Ilyen biztos, hogy van, mert Második ezen stratégia mellett pontosan 9 oszlopot fejez be, a többi 9 oszlop pedig (a kezdőoszlopot nem számolva, hiszen ott mindenképpen Kezdő rakja az utolsó számot) csak akkor telhet meg, ha Kezdő egy ilyen esetben oda rakja a számát, tehát marad bennük addig hely.
Így B≤10, hiszen minden oszlopban legfeljebb eggyel nagyobb az 1-esek száma, mint a 0-áké, mivel az utolsó lépés kivételével az oszlopban bármely játékos minden egyeséhez tartozik a másik játékosnak egy-egy különböző 0-ja. Másrészt összesen (19⋅19-1)/2=180 darab 1-es van a táblázatban, mivel a legelső lépésen kívül minden lépéspár (Második, majd Kezdő lépése) során a beírt számok összege 1. Ebből a skatulyaelv miatt következik, hogy a 19 sor egyikében legalább 10 az 1-esek száma, tehát A≥10≥B, vagyis Második nem nyerhet.

 

Ezután azt mutatjuk meg, hogy Második számára is létezik nem vesztő stratégia (lényegében ugyanaz, mint Kezdőé, csak sorokra alkalmazva).
Második írjon Kezdő utolsó leírt számának sorába másmilyen számot; amikor pedig nem tud, akkor egy olyan sorba írja a másmilyen számot, ahová még nem írt számot ilyen helyzetben. Ez lehetséges, hiszen a stratégia szerint Kezdő pontosan 10 sort fejez be, ekkor kell Másodiknak önállóan lépnie, és ahová lép, ott onnantól Kezdő lépése után páros sok szám lesz, tehát azokat Kezdő nem tudja befejezni. Így 10 sort Kezdő fejez be, 9 sorba pedig Második rak önállóan egy-egy számot, ezeken a számokon kívül pedig minden sorban ugyanannyi 1 és 0 van. Tehát minden sorban legfeljebb 10 darab 1-es van. Összesen 180 vagy 181 darab 1-es van a táblázatban (Kezdő utolsó számától függően), tehát a skatulya-elv szerint kell lennie olyan oszlopnak, ahol legalább 10 darab 1-es van. A≤10≤B, vagyis Kezdő nem nyerhet.
Mivel mindkét félnek van olyan stratégiája, melyet használva a másik fél nem nyerhet, egyik fél számára sem létezik nyerő stratégia.
 

Czett Mátyás (Zalaegerszegi Zrínyi M. Gimn., 12. évf.)