Od zarania dziejów gry dostarczały rozrywki, ćwiczyły umysły, a często stawały się źródłem dochodu. Nic dziwnego, że szanse zwycięstwa czy strategie wygrywające stały się przedmiotem matematycznych badań. Dziś napiszę o prostej zabawie kartami z elegancką teorią matematyczną. Na jej kanwie zademonstruję jak prowadzi się proces uogólniania, a także wskażę głębokie związki zaprezentowanych uogólnień z teorią macierzy i statystyką. Zapraszam do lektury.
Niedawno w moje ręce trafiło ciekawe zadanie pochodzące z Facebookowej strony Olimpiady Matematycznej Juniorów (adresowanej do uczniów szkół podstawowych). Oto jego treść.
Marek gra ze swoim kolegą w grę, w której obaj wykonują na zmianę ruchy. Na początku na stole leżą 43 karty. Ruch polega na zdjęciu ze stołu jednej, dwóch, trzech, lub czterech kart. Wygrywa ten z graczy, który zdejmie ostatnią kartę. Wiedząc, że zaczyna Marek, rozstrzygnij, który z graczy będzie mógł wygrać niezależnie od tego, jakie ruchy zrobi jego przeciwnik.
Nie jest ono specjalnie trudne do rozwiązania. Zauważmy, że jeśli Marek w pierwszym ruchu weźmie ze stołu trzy karty zostawiając 40 kart, to wygrywa. Istotnie, jeśli przeciwnik zabierze \(n\) kart (gdzie \(n\in\{1,2,3,4\}\)), to wystarczy, aby Marek w kolejnym ruchu zabrał \(5-n\) kart. Tak więc w każdej z ośmiu sekwencji dwóch ruchów przeciwnik–Marek ze stołu ubywa po 5 kart, a ostatni ruch należy do Marka.
Zauważmy, że liczba 43 kart na stole jest tylko umowna. Prawdziwa talia liczy 52 karty. Wtedy Marek inicjuje rozgrywkę zabierając dwie karty i dalej postępuje wg powyższego przepisu. A jeśli na na stole mamy dowolną liczbę kart, to wystarczy, aby Marek zabrał w pierwszym ruchu tyle kart, ile wynosi reszta z dzielenia ich liczby przez 5. Jeśli jednak na stole mamy liczbę kart podzielną przez 5, to Marek przegrywa, gdy przeciwnik zastosuje identyczną strategię. Tak więc zawsze, niezależnie od początkowej liczby kart, dla któregoś z graczy istnieje strategia wygrywająca. Ta prosta obserwacja jest pierwszym z dwóch uogólnień, które zaproponuję. Dotyczy ono liczebności użytej w rozgrywce talii kart.
Można jednak pójść znacznie dalej przypatrując się liczbom kart, które można zebrać ze stołu. Były to liczby 1, 2, 3, 4. Stanowią one ciąg arytmetyczny. Ale nie to decyduje i istnieniu strategii wygrywającej dla Marka, lecz inna, ciekawsza własność: suma dwóch skrajnych liczb jest równa sumie liczb środkowych. Jeśli ciąg jest arytmetyczny, to rzeczywiście ma ona miejsce. Ale nie tylko ciągi arytmetyczne ją spełniają. Wystarczy mieć cztery liczby dodatnie \(a,b,c,d\) o tej własności, że \(a<b\xle c<d\) oraz \(a+d=b+c\). Jeśli teraz \(K\) jest liczbą kart na stole przed rozpoczęciem rozgrywki, Marek w pierwszym ruchu zabiera \(K\bmod{(a+d)}\) kart (czyli resztę z dzielenia \(K\) przez \(a+d\)), a następnie po każdym z ruchów przeciwnika zabiera dopełnienie zabranej prze niego liczby kart do \(a+d\). Należy więc jeszcze zadbać o to, aby \(K\bmod{(a+d)}\in\{a,b,c,d\}\). Wtedy oczywiście Marek wygrywa. Jeśli jednak początkowa liczba kart jest wielokrotnością \(a+d\), wygrywa przeciwnik. A co stanie się, gdy \(K\bmod{(a+d)}\not\in\{a,b,c,d\}\)? Analizę tego przypadku pozostawiam Czytelnikom.
Przyjrzyjmy się teraz dwóm przykładom rozgrywek, które wygrywa Marek.
- Na stole znajduje się 76 kart, a liczby kart, które można zbierać to 2, 4, 8, 10. Wtedy \(2+10 = 4+8\) i strategia wygrywająca Marka to najpierw wziąć ze stołu 4 karty tak, aby liczba pozostałych kart, czyli 72, była podzielna przez 12. Jeśli przeciwnik weźmie 2, 4, 8 lub 10 kart, Marek zabierze odpowiednio 10, 8, 4 lub 2 karty i po sześciu sekwencjach po dwa ruchy wygrywa.
- Na stole mamy 95 kart, a zbierać można 3, 7 lub 11 kart. Wtedy \(3+11=7+7\), więc szukamy reszty z dzielenia przez 14. Początkowy ruch Marka to zabranie ze stołu 11 kart (bo \(95\bmod{14}=11\)), i pozostawienie 84 kart czyli liczby podzielnej przez 14. Jeśli przeciwnik zabierze 3 karty, to Marek weźmie 11 kart. A jeśli przeciwnik zabierze 11 kart, Marek weźmie 3. A jeśli przeciwnik zabierze 7 kart, to Marek również 7. Tak więc w każdej z sekwencji dwóch ruchów sumy zebranych przez obu graczy kart wynoszą 14 i znów Marek wygrywa.
Występujący w mojej propozycji uogólnienia warunek \(a+d=b+c\) wiąże się silnie z tzw. majoryzacją, o której napisano wiele książek i artykułów naukowych. Na uwagę zasługuje tu trzecia pozycja spisu literatury przywołanego artykułu z Wikipedii, czyli monografia Arnolda, Marshalla i Olkina. Ostatniego z autorów miałem okazję poznać osobiście w roku 2007 podczas jednej z konferencji matematycznych. Był prowadzącym sesję (chairmanem), podczas której wygłosiłem referat o ograniczeniach błędów kwadratur. Pogratulował mi dobrego wystąpienia. Byłem dumny, że mogłem uścisnąć dłoń tak wielkiej matematycznej sławy. Wspomniałem na początku, że majoryzacja ma silne związki z teorią macierzy, a stosuje się ją w wielu działach matematyki, m. in w statystyce przy interpretacji tzw. współczynnika koncentracji Giniego czy badaniu jakości klasyfikatorów binarnych za pomocą krzywych ROC. Ale temat wydaje się tak szeroki, że warto poświęcić mu cykl artykułów, który napiszę, jeśli będzie zapotrzebowanie.
Ostatnie uogólnienie, które zaproponuję, pozostawię do analizy Czytelnikom. Dotychczas analizowaliśmy trzy lub cztery liczby kart możliwych do zebrania w każdym ruchu. Co można powiedzieć, gdy będziemy mieć więcej możliwości, np. jeśli można zebrać 1, 2, 3, 4 lub 5 kart? A tymczasem cieszmy się grami, niech dalej rozwijają nasze szare komórki.