Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Oto ostatni z cyklu kącików poświęconych teorii gier. Rozważymy tu jedno – ale za to jakie! – zadanie dwunaste z zawodów I stopnia LXI Olimpiady Matematycznej. Jego autorem jest Jakub Onufry Wojtaszczyk. Na potrzeby kącika nieznacznie zmodyfikowałem i ograniczyłem treść do „trudniejszej połowy”, choć „łatwiejsza połowa”, obejmująca przypadek \(c\ge2,\) wcale do łatwych nie należy. Zadanie rozwiązało tylko trzech uczestników spośród 1517 startujących z całej Polski.
Zadanie. Ustalmy liczbę dodatnią \(c<2.\) Gracze \(K\) i \(F\) grają w \(c\)–fasolki, a reguły gry są następujące. Mamy \(n\ge2\) kubków, na początku wszystkie są puste. W każdej rundzie gracz \(K\) wskazuje dwa rozłączne, niepuste zbiory kubków, a gracz \(F\) wybiera jeden ze wskazanych zbiorów i dokłada po jednej fasolce do każdego z kubków w tym zbiorze. Celem gracza \(K\) jest doprowadzenie w co najwyżej \(\lfloor cn\rfloor\) rundach do tego, by w każdym kubku była inna liczba fasolek. Udowodnić, że dla wystarczająco dużych \(n\) gracz \(F\) ma strategię wygrywającą.
Rozważmy najpierw dowolną grę i niech \(\sigma\) będzie funkcją, która każdej pozycji przypisuje pewną liczbę. Taką funkcję nazywamy funkcją oceny pozycji, a jej wartości – ocenami. Strategię gracza (I lub II) nazwiemy minimalizującą funkcję \(\sigma\), jeśli zawsze nakazuje wykonać ruch do takiej pozycji, której ocena jest najniższa. Metoda, którą zastosujemy, polega na znalezieniu odpowiedniej funkcji, a następnie uzasadnieniu, że minimalizująca ją strategia jest wygrywająca. Przykład takiego rozumowania jest w poprzednim kąciku – stosowaliśmy strategię minimalizującą potencjał.
Przewodnik po rozwiązaniu zadania.
Krok 1 – strategia. Kubkowi, w którym jest \(k\) fasolek, przypiszemy nieujemną wagę \(w(k),\) która rośnie wraz z \(k.\) Jako ocenę \(\sigma(T)\) pozycji \(T\) przyjmiemy sumę wag wszystkich kubków. Celem gracza \(F\) jest utrzymanie, jak długo się da, nierówności \[\sigma(T)<w(n-1),\] bo jeśli ona zachodzi, to w każdym kubku jest co najwyżej \(n-1\) ziaren fasoli, co oznacza, że pewne dwa kubki mają ich tyle samo. Dalej zakładamy, że gracz \(F\) stosuje strategię minimalizującą funkcję \(\sigma.\)
Krok 2 – kontrola oceny pozycji. Załóżmy, że w pewnej pozycji \(T\) gracz \(K\) wskazał zbiory \(Z_1\) i \(Z_2,\) a ich wybór przez gracza \(F\) prowadzi do pozycji, odpowiednio, \(T_1\) i \(T_2.\) Niech \(T^+\) będzie pozycją powstałą z pozycji \(T\) przez dodanie po jednej fasolce do każdego kubka. Zbiory \(Z_1\) i \(Z_2\) są rozłączne, więc \[\big(\sigma(T_1)-\sigma(T)\big) + \big(\sigma(T_2)-\sigma(T)\big) \le \sigma(T^+)-\sigma(T),\] równoważnie \(\sigma(T_1)+\sigma(T_2)\le\sigma(T)+\sigma(T^+).\) W takim razie po rundzie ocena pozycji nie przekroczy \(\frac{\sigma(T)+\sigma(T^+)}{2},\) niezależnie od \(Z_1\) i \(Z_2.\)
W tym miejscu wypadałoby spróbować dwóch podejść – w pierwszym o ile, a w drugim ile razy zwiększy się ocena pozycji po rundzie? Pozostawiam Czytelnikowi samodzielne przekonanie się, że pierwsze z nich nie prowadzi do żadnego ciekawego wniosku. Zajmiemy się zatem drugim.
Krok 3 – funkcja oceny. Wiemy już, że jeśli \(T'\) jest pozycją po jednej rundzie od pozycji \(T,\) to \[\sigma(T') \le \sigma(T)\cdot\tfrac12\left(1+\tfrac{\sigma(T^+)}{\sigma(T)}\right).\] Wygodnie by było, gdyby czynnik z prawej był niezależny od \(T.\) W tym celu można wziąć \({w(k)=a^k}\) dla pewnego \(a>1.\) Wtedy \(\sigma(T^+)=a\sigma(T)\) oraz \({\sigma(T') \le \sigma(T)\cdot\frac{a+1}{2}}.\) Ocena pozycji początkowej jest równa \(n,\) więc po \(t\) rundach nie przekroczy ona \(n\left(\frac{a+1}{2}\right)^t.\)
Wykażemy, że funkcja \(\sigma\) z wagami jak wyżej i odpowiednim \(a\) jest tym, czego nam trzeba. Chcemy, żeby po \(\lfloor cn\rfloor\) rundach ocena pozycji była mniejsza niż \(w(n-1),\) do czego wystarczy, by zachodziła nierówność \[\tag{1} \label{BB1} n\left(\tfrac{a+1}{2}\right)^{cn} < a^{n-1}.\] Wykażemy, że jest ona prawdziwa dla wszystkich dostatecznie dużych \(n.\)
Krok 4 – technikalia. Po przekształceniach i podstawieniu \(a=1+2\varepsilon\) nierówność (1) przybiera postać \[\tag{2} \label{BB2} \sqrt[n]{an}(1+\varepsilon)^c<1+2\varepsilon.\] Zauważmy, że \[(1+\varepsilon)^c<1+2\varepsilon \ \ \ \iff \ \ \ \tfrac{(1+\varepsilon)^c-1^c}{\varepsilon}<2.\] W granicy \(\varepsilon\to0\) lewa strona drugiej nierówności jest pochodną funkcji \(x\mapsto x^c\) w punkcie \(x=1,\) która jest równa \(c,\) a pamiętamy, że \(c<2.\) Wobec tego można tak dobrać stałe \(\varepsilon,\delta>0,\) by zachodziła równość \[(1+\delta)(1+\varepsilon)^c = (1+2\varepsilon).\] Po podstawieniu tego do nierówności (2) otrzymamy \[\sqrt[n]{an} < 1+\delta.\] Prawa strona jest niezależna od \(n,\) a lewa ma granicę \(1\) przy \(n\to\infty,\) a więc ta nierówność – a tym samym nierówność (1) – jest prawdziwa przy odpowiednio ustalonym \(a\) dla wszystkich wystarczająco dużych \(n.\)
Udowodniliśmy zatem, że dla dużych \(n\) strategia minimalizująca funkcję \(\sigma,\) z odpowiednio dobraną stałą \(a,\) pozwala graczowi \(F\) przetrwać co najmniej \(\lfloor cn\rfloor\) rund.