Problem B. 5288. (January 2023)

B. 5288. Two players are playing the following game on a \(\displaystyle 8 \times 8\) chessboard. They take turns in selecting one side of a field of the chessboard, separating two adjacent fields of the board, and colouring it yellow. The player who is first forced to create a closed yellow polygon will lose the game. Which player has a winning strategy?

Based on an American competition problem

(4 pont)

Deadline expired on February 10, 2023.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

68 students sent a solution.
4 points:	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 points:	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 points:	7 students.
1 point:	8 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2023