Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Gra kółko i krzyżyk jest szczególnym przypadkiem gier \(\texttt{MM}\) (ang. maker-maker), które określamy następująco. Skończony zbiór \(\Omega\) jest planszą, niektóre jego podzbiory nazywamy wygrywającymi; przez \(\mathcal{W}\) będziemy oznaczać ich rodzinę. Gracz I (czerwony) koloruje elementy zbioru \(\Omega\) na czerwono, a gracz II (niebieski) – na niebiesko. Celem każdego gracza jest pokolorowanie w całości jednego ze zbiorów wygrywających (używa się również określenia zajęcie lub zbudowanie).
Argument kradzieży strategii (zob. poprzedni kącik) pozwala wykazać, że gra \(\texttt{MM}\) jest wygrana dla gracza I lub remisowa. Tutaj podamy naturalną strategię gracza II, która niekiedy gwarantuje mu remis. Idea jest następująca – gracz niebieski zapomina o tym, że ma zajmować zbiory wygrywające i skupi się jedynie na przeszkadzaniu w tym czerwonemu.
W ustalonej pozycji \(T,\) dla każdego zbioru \(W\in\mathcal{W},\) zdefiniujemy jego potencjał \(\rho_T(W),\) który jest tym większy, im łatwiej gracz I może ten zbiór w całości zająć. Kluczowe będą następujące warunki:
\(0\le\rho_T(W)\le1,\) a potencjał równy \(1\) mają wyłącznie całe czerwone zbiory;
po pokolorowaniu jednego z elementów na niebiesko potencjał danego zbioru zeruje się;
po pokolorowaniu jednego z elementów na czerwono potencjał danego zbioru wzrasta dwukrotnie.
Tylko jedna funkcja je spełnia: \[\rho_T(W) = \begin{cases} 1/2^b & \text{jeśli czerwonemu brakuje } b \text{ elementów} \\[-3pt]&\text{do zajęcia zbioru } W ,\\ 0 & \text{jeśli zbiór } W \text{ ma co najmniej} \\[-3pt]&\text{jeden element niebieski.}\end{cases}\] Potencjałem pozycji \(T\) nazwiemy sumę potencjałów wszystkich zbiorów wygrywających i oznaczymy go przez \(\sigma(T).\) Odnotujmy, że jeśli \(\sigma(T)<1,\) to na mocy (1) gracz czerwony nie ma jeszcze żadnego zbioru wygrywającego.
Dla niepokolorowanego \(x\in\Omega\) w pozycji \(T\) niech \(g_T(x)\) oznacza sumę potencjałów wszystkich zbiorów wygrywających, zawierających \(x.\) Pokolorowanie elementu \(x\) na niebiesko skutkuje zmniejszeniem \(\sigma(T)\) o \(g_T(x)\) (warunek (2)), a na czerwono – zwiększeniem o \(g_T(x)\) (warunek (3)).
Najbardziej naturalna strategia gracza II to minimalizacja sumy wszystkich potencjałów lub równoważnie – kolorowanie takiego \(x,\) dla którego wartość \(g_T(x)\) jest najwyższa.
Przypuśćmy, że \(T_0\) jest pozycją z ruchem niebieskiego gracza, który koloruje optymalny element \(x,\) przechodząc do pozycji \(T_1.\) Następnie gracz czerwony koloruje element \(y,\) przechodząc do pozycji \(T_2.\) Mamy \({\sigma(T_2) = \sigma(T_0)-g_{T_0}(x)+g_{T_1}(y)},\) a ponadto \(g_{T_1}(y) \le g_{T_0}(y) \le g_{T_0}(x),\) więc \({\sigma(T_1)\le\sigma(T_2)\le\sigma(T_0)}.\) Strategia gracza II gwarantuje zatem, że do samego końca rozgrywki potencjał pozycji nigdy nie przekroczy \(\sigma(T_0).\) W takim razie wykazaliśmy:
Twierdzenie Erdősa–Selfridge’a. Jeśli w grze \(\texttt{MM}\) gracz I nie może w pierwszym ruchu otrzymać pozycji z potencjałem co najmniej \(1,\) to gra jest remisowa.*
W praktyce sprawdza się, czy potencjał pozycji początkowej jest mniejszy niż \(\frac12,\) gdyż gracz I w swoim ruchu może co najwyżej podwoić potencjał pozycji.
Zadania
Oznaczmy przez \(\texttt{KK}(n,k)\) uogólnioną grę kółko i krzyżyk – na planszy \(n\times n\) wygraną daje \(k\) znaczków pod rząd (pionowo, poziomo lub skośnie). Wykazać, że jeśli \(k\ge2\log_2n+3,\) to gra \(\texttt{KK}(n,k)\) jest remisowa.
Wskazówka Liczba zbiorów wygrywających jest mniejsza niż \(4n^2,\) więc potencjał pozycji początkowej jest mniejszy niż \(4n^2/2^k.\)
Ciekawostka 1. Alfred W. Hales i Robert I. Jewett podali elegancki dowód metodą strategii ruchów odpowiadających,
że jeśli \(k\ge 9,\) to dla każdego \(n\) gra \(\texttt{KK}(n,k)\) jest remisowa (1963).
Ciekawostka 2. Niech \(W(n,k)\) oznacza stwierdzenie, że gra \(\texttt{KK}(n,k)\) jest wygrana dla gracza I, a \(D(n,k)\) – że jest remisowa. Intuicja podpowiada, że:
(1) \(W(n,k) \Rightarrow W(n+1,k)\);
(2) \(D(n,k) \Rightarrow D(n,k+1).\)
Jest to najbardziej frustrujący problem teorii gier – nikomu jeszcze nie udało się ani udowodnić, ani obalić żadnej z powyższych implikacji (choć są one prawdziwe dla podobnej klasy gier – maker-breaker).Gracze na zmianę kolorują, każdy swoim kolorem, krawędzie dwudziestościanu ściętego („piłki nożnej”), a zwycięstwo daje pokolorowanie wszystkich krawędzi należących do jednej ze ścian. Rozstrzygnąć tę grę.
Wskazówka Potencjał pozycji po dowolnym pierwszym ruchu gracza I jest mniejszy niż \(1.\)
Dane są liczby naturalne \(k\ge3\) oraz \(n<2^{k/2}.\) Udowodnić, że liczby \(1,2,\ldots,n\) można pokolorować dwoma kolorami w taki sposób, żeby żadne \(k\) liczb tego samego koloru nie tworzyło ciągu arytmetycznego.
Wskazówka Rozważmy grę na planszy \(\Omega=\{1,2,\ldots,n\},\) w której rodzinę \(\mathcal{W}\) stanowią \(k\)-wyrazowe postępy arytmetyczne. Ta gra jest remisowa, więc wystarczy wziąć kolorowanie z pozycji końcowej w remisowej rozgrywce.
Ustalmy stałą \(c\in[0,1].\) Rozważmy grę na planszy \(n\times n\) podobną do uogólnionego kółka i krzyżyka. Celem jest uzyskanie co najmniej \(cn\) znaczków w jednej linii poziomej lub pionowej, ale niekoniecznie pod rząd. Wykazać, że istnieją stałe \(c_0,c_1\in(0,1)\) o następującej własności:
jeśli \(c>c_0,\) to gra jest remisowa dla dostatecznie dużych \(n\);
jeśli \(c<c_1,\) to gra jest wygrana dla dostatecznie dużych \(n.\)
Wskazówka Nietrudno zauważyć, że \(c_1=\frac 12\) spełnia nasze oczekiwania. Dalej niech \(c>\frac 12\) i zapiszmy \(c=1-\varepsilon.\) Z wykorzystaniem oszacowania \(\binom{n}{k}\le(en/k)^k\) dla \(k=\varepsilon n\) dowodzimy, że jeśli zachodzi nierówność \(4n < \bigl(2\bigl(\frac{\varepsilon}{2e}\bigr)^\varepsilon\bigr)^n,\) to potencjał pozycji początkowej jest mniejszy od \(\frac 12.\) Chcielibyśmy, żeby \(\bigl(\frac{\varepsilon}{2e}\bigr)^\varepsilon>\frac 12.\) Jest tak dla \(\varepsilon<\varepsilon_{\max}\approx 0{,}2378,\) więc można wziąć \(c_0=1-\varepsilon_{\max}.\)
Ciekawostka. József Beck wykazał, że teza jest prawdziwa dla \(c_0=c_1=\frac 12\) (2008).
* Sformułowanie, na potrzeby kącika, jest nieco inne niż oryginalne.