A B. 5261. feladat (2022. szeptember)

B. 5261. Kezdő és Második a 100 csúcsú teljes gráf élein játszanak. Felváltva lépnek, Kezdő minden lépésnél egy még ki nem színezett élt pirosra, Második pedig minden lépésnél egy (még ki nem színezett) élt kékre színez. A játék akkor ér véget, ha vagy van 4 olyan csúcs, melyek között mind a 6 él piros, ekkor Kezdő nyer; vagy van 4 olyan csúcs, melyek között mind a 6 él kék, ekkor Második nyer; vagy pedig egyik sem teljesül, és nincs több beszínezhető él, ekkor az eredmény döntetlen. Kinek van nyerő stratégiája?

(6 pont)

A beküldési határidő 2022. október 10-én LEJÁRT.

Megoldás. Először belátjuk, hogy a játék nem végződhet döntetlennel, ugyanis ha egy 100 csúcsú gráf éleit pirossal és kékkel színezzük, biztosan lesz 4 olyan csúcs, melyek között mind a 6 él egyforma színű.

Tegyük fel, hogy a 100 csúcsú teljes gráf összes élét kiszíneztük pirosra vagy kékre. Legyen \(\displaystyle A_0\) egy tetszőleges csúcs. A másik 99 csúcs közül legalább 50-be \(\displaystyle A_0\)-ból egyforma színű él indul, legyen ezen csúcsok halmaza \(\displaystyle S_1\), a közös szín pedig \(\displaystyle c_1\). Tehát \(\displaystyle |S_1|\geq 50\), és minden \(\displaystyle S_1\)-beli csúcs \(\displaystyle c_1\) színű éllel van összekötve \(\displaystyle A_0\)-lal.

Most vegyünk egy \(\displaystyle A_1\in S_1\) csúcsot. A többi, legalább 49 darab \(\displaystyle S_1\)-beli csúcs közül legalább 25-tel egyforma színű él köti össze \(\displaystyle A_1\)-et, van tehát egy \(\displaystyle S_2\subseteq S_1\setminus\{A_1\}\) csúcshalmaz és egy \(\displaystyle c_2\) szín, hogy minden \(\displaystyle A_2\) és \(\displaystyle S_2\) között futó él színe \(\displaystyle c_2\), továbbá \(\displaystyle |S_2|\geq 24\). Ezt folytatva, kapjuk csúcsok egy \(\displaystyle A_0,A_1,A_2,A_3,A_4\) sorozatát, színek \(\displaystyle c_1,c_2,c_3,c_4, c_5\) sorozatát és csúcshalmazok \(\displaystyle S_1\supset S_2 \supset S_3\supset S_4 \supset S_5\) sorozatát úgy, hogy \(\displaystyle A_i\in S_i\) és minden \(\displaystyle A_{i-1}\) és \(\displaystyle S_i\) közti él színe \(\displaystyle c_i\), továbbá \(\displaystyle |S_1|\geq 50, |S_2|\geq 25, |S_3|\geq 12, |S_4|\geq 6, |S_5|\geq 3\).

A \(\displaystyle c_1,c_2,c_3,c_4,c_5\) színek mindegyike piros vagy kék, így van köztük három egyforma, mondjuk \(\displaystyle c_i=c_j=c_k=:c\) az \(\displaystyle 1\leq i<j<k\leq 5\) indexekre. Válasszuk ki az \(\displaystyle A_{i-1},A_{j-1},A_{k-1}\) csúcsokat és az egyik \(\displaystyle S_5\)-beli \(\displaystyle A_5\) csúcsot. Ezen 4 csúcs között minden él \(\displaystyle c\) színű, hiszen \(\displaystyle A_{j-1},A_{k-1},A_5\in S_i, A_{k-1},A_5\in S_j,A_5\in S_k \).

Tehát egy 2 színnel színezett 100 csúcsú teljes gráfban lesz 4 csúcs, melyek között minden él egyforma színű.

Megjegyezzük, hogy a Ramsey-elméletből ismert, hogy valójában bármely \(\displaystyle k\) és \(\displaystyle \ell\) pozitív egész számok esetén létezik egy olyan \(\displaystyle R(k,\ell)\) egész szám, hogy az \(\displaystyle R(k,\ell)\) csúcsú teljes gráf éleit színezve piros-kék színekkel biztosan lesz \(\displaystyle k\) csúcs, hogy köztük minden él piros vagy lesz \(\displaystyle \ell\) csúcs, melyek között minden él kék, de \(\displaystyle R(k,\ell)-1 \) csúcsú teljes gráfra ez még nem igaz. Mi azt igazoltuk, hogy \(\displaystyle R(4,4)\leq 100\), ismert, hogy valójában \(\displaystyle R(4,4)=18\).

Tehát a játék döntetlennel nem érhet véget. Most belátjuk, hogy a két játékos közül valakinek biztosan van nyerő stratégiája. A játék során véges sok féle állapot képzelhető el, éspedig az olyan részleges színezések, amikor a 100 csúcsú teljes gráf néhány éle piros, néhány éle kék, vagy ugyanannyi piros és kék él van, vagy 1-gyel több piros van, mint kék, valamint még nincs egyszínű négyes. (Mivel az élek száma \(\displaystyle \binom{100}{2}=4950\), ezért az állapotok száma legfeljebb \(\displaystyle 2^{4950}\).) Azt fogjuk belátni, hogy minden állapot ``nyerő'' vagy ``vesztő'', ahol a ``nyerő'' azt jelenti, hogy a soron következő játékos megfelelő stratégia esetén biztosan nyer, a ``vesztő'' pedig azt, hogy a soron következő játékos ellenfele megfelelő stratégia esetén biztosan nyer. (Megjegyezzük, hogy a színezett élek számának paritása alapján mindig egyértelmű, ki az éppen soron következő játékos.) Például azok az állapotok, ahol a soron következő játékos egyetlen még színezetlen él színezésével létre tud hozni egy olyan négyest, melynek mind a hat éle az ő színével van színezve, nyerő állapotok.

Ismételjük a következő gondolatmenetet, amíg minden állapotról meg nem határozzuk, hogy nyerő vagy vesztő: Az olyan állapotok közül, amelyekről még nem tudjuk se azt, hogy nyerő, se azt, hogy vesztő, vegyünk egy olyat, amiben a legtöbb színezett él van. Tudjuk, hogy a soron következő játékos bármelyik élet is színezi ki, vagy véget ér a játék a győzelmével, vagy olyan állapotba kerülünk, amiről tudjuk, hogy nyerő vagy vesztő. Ha egy lépésben nyerni tud, akkor az állapot értelemszerűen nyerő. Ha nem tud, de tud vesztő állapotot létrehozni, akkor szintén nyerő az állapot, hiszen olyan állást tud létrehozni, ami a soron következő, másik játékos számára vesztő. Végül, ha csak nyerő állapotokat tud kialakítani, akkor az állapot vesztő, hiszen bármit is lép, a másik játékosnak lesz nyerő stratégiája.

Ezzel véges sok lépésben minden állapotról eldönthető, hogy nyerő vagy vesztő, tehát valamelyik játékosnak van nyerő stratégiája: ha a kiindulási állapot – amikor még nincs színezett él – nyerő, akkor a Kezdőnek, ha vesztő, akkor a Másodiknak. Megjegyezzük, hogy itt a játékról csak annyit használtunk, hogy kétszemélyes, véges sok állapot van, mindig pontosan az egyik játékos nyer, és mindenki végig minden információval rendelkezik (speciálisan a véletlen sem játszik szerepet).

Tehát tudjuk, hogy a két játékos közül valakinek (pontosan az egyiküknek) van nyerő stratégiája. A ,,stratégiaellopás'' módszerével megmutatjuk, hogy ez csak Kezdő lehet.

Tegyük fel ugyanis indirekten, hogy Másodiknak van egy nyerő stratégiája. Ennek segítségével belátjuk, hogy Kezdőnek is van nyerő stratégiája, ez azonban nem lehetséges. Kezdő először egy tetszőleges \(\displaystyle e\) élt pirosra színez, majd innentől úgy képzeli, mintha minden még színezetlen lenne, és valójában Második kezdené a játékot, ő pedig Második nyerő stratégiáját alkalmazva játszik tovább (a színek szerepét felcserélve). Az \(\displaystyle e\) élt természetesen Második már nem színezheti ki, de ez csak az ő lépéslehetőségeit korlátozza, Kezdő tudja alkalmazni a tőle ,,lopott'' stratégiát. Elképzelhető viszont, hogy a stratégia szerinti játékot követve egy ponton Kezdőnek az \(\displaystyle e\) élt kellene pirosra színeznie. Ekkor választ egy színezetlen \(\displaystyle e'\) élt, azt pirosra színezi, és innentől kezdve \(\displaystyle e'\)-t képzeli színezetlennek, \(\displaystyle e\)-ről pedig a képzeletében is tudatosítja, hogy az már piros. Ezt a stratégiát folytatva végül nyerni fog, ha Másodiké valóban nyerő stratégia volt. Ez persze nem lehet (mindkét játékosnak nem lehet nyerő stratégiája egyszerre), így Másodiknak nem lehet nyerő stratégiája.

Ezzel beláttuk, hogy Kezdőnek van nyerő stratégiája.

Statisztika:

38 dolgozat érkezett.
6 pontot kapott:	Csonka Illés, Duchon Márton, Fülöp Csilla, Kovács Benedek Noel, Nguyen Kim Dorka, Seres-Szabó Márton, Simon László Bence, Szakács Ábel, Varga Boldizsár, Wiener Anna, Zömbik Barnabás.
5 pontot kapott:	Bényei Borisz, Csilling Dániel, Czanik Pál, Juhász-Molnár Erik, Tarján Bernát.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	10 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2022. szeptemberi matematika feladatai