A B. 5288. feladat (2023. január)

B. 5288. Két játékos a következő játékot játssza egy \(\displaystyle 8 \times 8\)-as sakktáblán. A játékosok felváltva lépnek, egy lépésben egy játékos a két szomszédos mezőt elválasztó szakaszok egyikét sárgára színezi. Az a játékos veszít, akinek a lépése után először jön létre egy olyan sokszög, amelynek minden oldala sárga. Melyik játékosnak van nyerő stratégiája?

(Amerikai versenyfeladat alapján)

(4 pont)

A beküldési határidő 2023. február 10-én LEJÁRT.

Megoldás. Jelölje \(\displaystyle \mathcal G\) az ábrán látható gráfot.

\(\displaystyle \mathcal G\) élei a játékban sárgára színezhető szakaszok, csúcsai azon rácspontok, ahol legalább egy ilyen szakasz véget ér. \(\displaystyle \mathcal G\) csúcsainak száma: \(\displaystyle (8+1) \cdot (8+1) - 4 = 77\). (\(\displaystyle \mathcal G\) éleinek száma pedig \(\displaystyle 2 \cdot 7 \cdot 8 = 112\), de ennek nincs érdemi szerepe a megoldásban.)

Feltehető, hogy mindkét játékos ,,értelmesen'' játszik, vagyis minden lépésében olyan élet színez sárgára, amely nem eredményez sárga kört \(\displaystyle \mathcal G\)-ben – feltéve, hogy az adott pillanatban létezik még ilyen él. Ha nem létezik, akkor a sárga színű élek (a hozzájuk tartozó csúcsokkal) egy olyan fa részgráfot alkotnak, amely \(\displaystyle \mathcal G\) összes csúcsát tartalmazza. (Az ilyen részgráfokat feszítő fának nevezzük.) Ennek bizonyításához tegyük fel, hogy ez nem így van: akkor a sárga élek által meghatározott \(\displaystyle \mathcal S\) részgráf körmentes, de vagy nem összefüggő, vagy nem tartalmazza \(\displaystyle \mathcal S\) összes csúcsát. (\(\displaystyle \mathcal S\) csúcsai azon \(\displaystyle \mathcal G\)-beli csúcsok, amelyek legalább egy sárga élnek végpontjai).

Tekintsük \(\displaystyle \mathcal S\) egy összefüggő \(\displaystyle \mathcal C\) komponensét; ez nem tartalmazhatja \(\displaystyle \mathcal G\) valamennyi csúcsát, és nem vezet ki belőle sárga él. Mivel \(\displaystyle \mathcal G\) összefüggő, létezik olyan él, amely \(\displaystyle \mathcal C\)-beli csúcsot köt össze egy \(\displaystyle \mathcal C\)-n kívüli csúccsal, egy ilyen élet sárgára színezve továbbra is körmentes sárga részgráfot kapunk, ellentmondás.

Egy fa éleinek a száma 1-gyel kevesebb a csúcsainak számánál; esetünkben a sárga színű feszítő fa éleinek száma \(\displaystyle 77-1=76\). Ez azt mutatja, hogy az a játékos, aki a 77-edik lépést kényszerül megtenni, veszít. Mivel 77 páratlan, ez éppen a játékot elkezdő játékos. Tehát a második játékos nyer.

Statisztika:

68 dolgozat érkezett.
4 pontot kapott:	Ali Richárd, Bencz Benedek, Bodor Mátyás, Chrobák Gergő, Diaconescu Tashi, Diószeghy Erzsébet, Domján Olivér, Fajszi Karsa, Fleischman Illés, Fórizs Emma, Fülöp Csilla, Hodossy Réka, Holló Martin, Horák Zsófia, Horváth 530 Mihály, Kerekes András, Kocsis 827 Péter, Kovács Benedek Noel, Mizik Lóránt, Molnár István Ádám, Nagy 292 Korina, Nguyen Kim Dorka, Petrányi Lilla, Prohászka Bulcsú, Sárdinecz Dóra, Sütő Áron, Szabó 810 Levente, Szakács Ábel, Szakács Domonkos, Szalontai Júlia, Szanyi Attila, Szegedi Ágoston, Szeibert Dominik, Tarján Bernát, Teveli Jakab, Tran Dávid, Varga Boldizsár, Vigh 279 Zalán, Wiener Anna.
3 pontot kapott:	Csilling Dániel, Czanik Pál, Czirják Márton Pál, Fodor Gergely, Keresztély Zsófia, László Anna, Melján Dávid Gergő, Nádor Artúr, Nagy 429 Leila, Pálfi András, Virág Lénárd Dániel.
2 pontot kapott:	7 versenyző.
1 pontot kapott:	8 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2023. januári matematika feladatai