![]() |
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 A0 egy tetszőleges csúcs. A másik 99 csúcs közül legalább 50-be A0-ból egyforma színű él indul, legyen ezen csúcsok halmaza S1, a közös szín pedig c1. Tehát |S1|≥50, és minden S1-beli csúcs c1 színű éllel van összekötve A0-lal.
Most vegyünk egy A1∈S1 csúcsot. A többi, legalább 49 darab S1-beli csúcs közül legalább 25-tel egyforma színű él köti össze A1-et, van tehát egy S2⊆S1∖{A1} csúcshalmaz és egy c2 szín, hogy minden A2 és S2 között futó él színe c2, továbbá |S2|≥24. Ezt folytatva, kapjuk csúcsok egy A0,A1,A2,A3,A4 sorozatát, színek c1,c2,c3,c4,c5 sorozatát és csúcshalmazok S1⊃S2⊃S3⊃S4⊃S5 sorozatát úgy, hogy Ai∈Si és minden Ai−1 és Si közti él színe ci, továbbá |S1|≥50,|S2|≥25,|S3|≥12,|S4|≥6,|S5|≥3.
A c1,c2,c3,c4,c5 színek mindegyike piros vagy kék, így van köztük három egyforma, mondjuk ci=cj=ck=:c az 1≤i<j<k≤5 indexekre. Válasszuk ki az Ai−1,Aj−1,Ak−1 csúcsokat és az egyik S5-beli A5 csúcsot. Ezen 4 csúcs között minden él c színű, hiszen Aj−1,Ak−1,A5∈Si,Ak−1,A5∈Sj,A5∈Sk.
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 k és ℓ pozitív egész számok esetén létezik egy olyan R(k,ℓ) egész szám, hogy az R(k,ℓ) csúcsú teljes gráf éleit színezve piros-kék színekkel biztosan lesz k csúcs, hogy köztük minden él piros vagy lesz ℓ csúcs, melyek között minden él kék, de R(k,ℓ)−1 csúcsú teljes gráfra ez még nem igaz. Mi azt igazoltuk, hogy R(4,4)≤100, ismert, hogy valójában 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 (1002)=4950, ezért az állapotok száma legfeljebb 24950.) 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 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 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 e élt kellene pirosra színeznie. Ekkor választ egy színezetlen e′ élt, azt pirosra színezi, és innentől kezdve e′-t képzeli színezetlennek, 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
|