% Ćwiczenia na Newtona o grach \mainlanguage[pl] \usetypescript[pagella] \setupbodyfont[pagella] \usemodule[tikz] \usetikzlibrary[calc] \let\origstarttikzpicture=\starttikzpicture \let\origstoptikzpicture=\stoptikzpicture \def\starttikzpicture{\hbox\bgroup\origstarttikzpicture} \def\stoptikzpicture {\origstoptikzpicture\egroup} \def\todo#1{{\em \kap{do dopisania}: #1}} %\setupinteraction[state=start] \enablemode[nauczyciel] %\disablemode[nauczyciel] \def\startteacher{\grabbufferdata[teacher][startteacher][stopteacher]} \doifmodeelse{nauczyciel}{\def\stopteacher{\par{\switchtobodyfont[small]\getbuffer[teacher]\par}}}{\def\stopteacher{}} \def\startanswer{\par\dostartbuffer[answer][startanswer][stopanswer]} \doifmodeelse{nauczyciel}{\def\stopanswer{{\switchtobodyfont[small]\blank[small]{\sl Odpowiedź.} \getbuffer[answer]\par}}}{\def\stopanswer{}} \def\putdotafter#1{#1.} \setuphead[subject][style=bold,after={},alternative=text,distance=0.25em,textcommand=\putdotafter] %\setuphead[section][numbercommand=\putdotafter] \setuphead[chapter][sectionstopper=.,page=no] \def\teacheronly#1{\doifmode{nauczyciel}{#1}} \def\time#1{\doifmode{nauczyciel}{\removeunwantedspaces \hskip 0pt plus 6em\penalty20\ \hskip 0pt plus -6em (#1~minut)}} \defineitemgroup[exercises] \setupitemgroup[exercises][1][n,broad,intro][left={\headnumber[chapter]},before={},inbetween={\blank[medium]}] \def\ppauza{\unskip\kern.2em--\hskip.2em\ignorespaces} \starttext \noheaderandfooterlines \startalignment[middle] \tfd Gry (materiały na ćwiczenia w~czwartek) \par\blank[big] \stopalignment \startnotmode[nauczyciel] \placefigure[bottom,none]{}{% \hbox to \textwidth{ \externalfigure[logo-1-t][height=1.5cm]\hfil \externalfigure[logo-2-t][height=1.5cm]\hfil \externalfigure[logo-3-t][height=1.5cm] }} \stopnotmode \completecontent[alternative=a,pagestyle=slanted,distance=2pt] \page \startchapter[title={Gry macierzowe\time{15--20}}] \startexercises \startitem Jakie są strategie optymalne dla obu graczy w~grze o~poniższej macierzy? \startformula \startmathmatrix[n=2,left={\left(\,},right={\,\right)},align=right] \NC 1 \NC 2 \NR \NC 3 \NC 4 \NR \stopmathmatrix \stopformula \startteacher Macierz interpretujemy następująco: I~gracz wybiera wiersz, II~gracz wybiera kolumnę (obaj robią to równocześnie), po czym II~gracz wypłaca pierwszemu kwotę z~przecięcia wybranego wiersza i~kolumny (gra o~sumie zero: wygrana jednego gracza jest równa przegranej drugiego). \stopteacher \startanswer Pierwszy gracz, wybierając drugi wiersz, w~każdym wypadku wygrywa więcej, niż gdyby wybrał pierwszy; powinien więc wybrać drugi wiersz (dominujący). Drugi gracz, wybierając pierwszą kolumnę, w~każdym przypadku traci mniej, niż gdyby wybrał drugą; powinien więc wybrać pierwszą (dominującą) kolumnę. \stopanswer \stopitem \startitem Rozważmy grę z~następującą macierzą: \startformula \startmathmatrix[n=3,left={\left(\,},right={\,\right)},align=right] \NC 4 \NC 1 \NC -1 \NR \NC 0 \NC 1 \NC 6 \NR \NC 3 \NC 2 \NC 5 \NR \stopmathmatrix \stopformula Jaka jest optymalna strategia dla każdego z~graczy? \startanswer Żaden wiersz ani kolumna nie są dominujące, ale ponieważ \math{2} w~trzecim rzędzie i~drugiej kolumnie jest {\em najmniejszą} wartością w~swoim rzędzie i~{\em największą} wartością w~swojej kolumnie, optymalną strategią dla I~gracza jest trzecia (wygra co najmniej~\math{2} niezależnie od strategii II~gracza), a~dla II~gracza druga (przegra co najwyżej~\math{2} niezależnie od strategii I~gracza). \stopanswer \stopitem \startitem Gra {\em parzyste czy nieparzyste} polega na tym, że dwóch graczy wybiera (równocześnie) liczbę \math{1} lub~\math{2}. Jeśli suma wybranych liczb jest nieparzysta, wygrywa gracz~I; jeśli jest parzysta, wygrywa gracz~II. Gracz, który przegrał, oddaje drugiemu kwotę równą sumie wybranych liczb. Narysujcie macierz tej gry. Jaka jest optymalna strategia każdego z~graczy? Czy gra jest sprawiedliwa? \startteacher To zadanie możemy opuścić lub omówić pobieżnie bez większej szkody. \stopteacher \startanswer Macierz: \startformula \startmathmatrix[n=2,left={\left(\,},right={\,\right)},align=right] \NC -2 \NC 3 \NR \NC 3 \NC -4 \NR \stopmathmatrix \stopformula Powyższa macierz nie ma strategii dominujących ani punktów siodłowych, trzeba więc zastosować inną metodę. Załóżmy, że gracz~I wybiera~\math{1} z~prawdopodobieństwem~\math{p} i~\math{2} z~prawdopodobieństwem~\math{1-p}. Wyznaczymy~\math{p} tak, żeby gracz~I wygrywał przeciętnie {\em tyle samo}, obojętnie, co zrobi gracz~II. Jeśli gracz~II wybierze~\math{1}, przeciętna wygrana~I wynosi \math{-2p+3(1-p)}. Jeśli II wybierze~\math{2}, przeciętna wygrana~I wynosi~\math{3p-4(1-p)}. Aby wartości te były równe, musi być \math{p=\frac{7}{12}}. Zatem gracz~I powinien wybrać~\math{1} z~prawdopodobieństwem \math{\frac{7}{12}}, a~\math{2} z~prawdopodobieństwem~\math{\frac{5}{12}}. Jego przeciętna wygrana wynosi \math{-2\frac{7}{12}+3\frac{5}{12}=3\frac{7}{12}-4\frac{5}{12}=\frac{1}{12}}. Prowadząc podobną analizę dla gracza~II widzimy, że ta sama strategia pozwala mu uzyskać przeciętną stratę~\math{\frac{1}{12}}. Wynika stąd, że znalezionej strategii nie da się ulepszyć, a~gra nie jest sprawiedliwa (preferuje I~gracza). \stopanswer \stopitem \startitem Rozważmy wariant gry {\em parzyste czy nieparzyste}, w~którym każdy z~graczy wybiera jedną z~liczb~\math{\{0,1,2\}}. Spróbujcie znaleźć optymalną strategię dla pierwszego gracza. \startteacher To zadanie opuszczamy, chyba że mamy grupę geniuszy. \stopteacher \startanswer Nie ma ani strategii dominujących, ani punktów siodłowych. Postępujemy jak w~poprzednim ćwiczeniu; okazuje się, że I~gracz powinien wybierać~\math{1} z~prawdopodobieństwem~\math{\frac{1}{2}} i~pozostałe liczby z~prawdopodobieństwem~\math{\frac{1}{4}}. Uwaga: ta metoda {\em nie działa dla każdej macierzy}! \stopanswer \stopitem \stopexercises \stopchapter \startchapter[title={Nim-suma liczb całkowitych nieujemnych\time{10--15}}] \startteacher Pojęcia nim-sumy {\em nie będzie} na wykładzie, trzeba je wprowadzić na ćwiczeniach. Jest to działanie w~zbiorze liczb całkowitych nieujemnych określone następująco: aby wyliczyć nim-sumę dwóch liczb, przeliczamy je na układ dwójkowy, dodajemy pisemnie bez przeniesienia (czyli cyfry na każdej pozycji {\em modulo}~\math{2}) i~wynik interpretujemy znów jako liczbę w~zapisie dwójkowym. Przykład: \startformula 6\oplus 12=(110)_2\oplus(1100)_2=(1010)_2=10. \stopformula (Okazuje się, że to działanie jest łączne i~przemienne, elementem neutralnym jest~\math{0}, każdy element jest swoją przeciwnością, a~ponadto nim-suma ma fundamentalne znaczenie dla analizy gry {\em Nim} i~pewnych innych gier.) \stopteacher \startexercises \startitem Przeliczcie następujące liczby w~zapisie dwójkowym na system dziesiątkowy: % \startsimplecolumns \startitemize[a,columns,two,joinedup][stopper=)] \startitem \math{(101)_2} \stopitem \startitem \math{(101011)_2} \stopitem \stopitemize % \stopsimplecolumns \startanswer \startitemize[a,text][stopper=] \startitem \math{(101)_2=2^0+2^2=1+4=5}; \stopitem \startitem \math{(101011)_2=1+2+8+32=43}. \stopitem \stopitemize \stopanswer \stopitem \startitem Przeliczcie następujące liczby na system dwójkowy: \startitemize[a,columns,two,joinedup][stopper=)] \startitem \math{10} \stopitem \startitem \math{77} \stopitem \stopitemize \startanswer \startitemize[a] \startitem \math{10=8+2=(1010)_2}; \stopitem \startitem Aby przeliczyć na system dwójkowy liczbę \math{77}, można np. dzielić ją przez~\math{2} (z~resztą) tak długo, aż otrzymamy zero, a~reszty wypisywać jako kolejne (od prawej strony) cyfry dwójkowe: \starttabulate[|r|] \NC \math{77:2=38~\text{r.}~1}\NR \NC \math{38:2=19~\text{r.}~0}\NR \NC \math{19:2=9~\text{r.}~1}\NR \NC \math{9:2=4~\text{r.}~1}\NR \NC \math{4:2=2~\text{r.}~0}\NR \NC \math{2:2=1~\text{r.}~0}\NR \NC \math{1:2=0~\text{r.}~1}\NR \stoptabulate Zatem \math{77=(1001101)_2}. \stopitem \stopitemize \stopanswer \stopitem \startitem Znajdźcie następujące nim-sumy: \startitemize[a,columns,two,joinedup,broad,intro][stopper=)] \startitem \math{18\oplus 0} \stopitem \startitem \math{13\oplus 13} \stopitem \startitem \math{10\oplus 77} \stopitem \startitem \math{10\oplus 6\oplus 12} \stopitem \stopitemize \startanswer \startitemize[a,text][stopper=] \startitem \math{18\oplus 0=18}; \stopitem \startitem \math{13\oplus 13=0}; \stopitem \startitem \math{10\oplus 77=71}; \stopitem \startitem \math{10\oplus 6\oplus 12=0} (ten przykład warto policzyć przynajmniej dwa razy, w~różnej kolejności!). \stopitem \stopitemize \stopanswer \stopitem \stopexercises \stopchapter \startchapter[title={Nim\time{20--25}}] \startsubject[title={Zasady gry}] Na trzech kupkach kładziemy kamienie (lub żetony, patyczki itp.). Gracze wykonują ruchy na przemian. Ruch polega na zabraniu dowolnej liczby kamieni (co najmniej jednego, być może wszystkich) z~dowolnej kupki. Gracz, który weźmie ostatni kamień, wygrywa. \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Rozegrajcie kilka partii (można zacząć np. od kupek liczących \math{5}, \math{7} i~\math{9} kamieni). Czy potraficie odkryć, który gracz ma strategię wygrywającą i~jak powinien grać, żeby wygrać? \stopitem \startitem Narysujcie graf {\em Nima} dla rozgrywki, która zaczyna się od kupek o~liczebnościach \math{1}, \math{1} i~\math{2}. (Wygodnie będzie opisać wierzchołki grafu trójkami liczb, np. \math{(1,1,2)}.) Znajdźcie N-pozycje i~P-pozycje. Przy każdej pozycji zapiszcie nim-sumę liczebności kupek. Czy zauważyliście pewną prawidłowość? \startteacher {\em N-pozycja} to pozycja, w~której {\em następny} gracz (czyli ten, czyja jest kolej) wygra, jeśli będzie grać prawidłowo (obojętnie, co zrobi drugi gracz). {\em P-pozycja} to pozycja, w~której {\em poprzedni} gracz (czyli ten, który do niej doprowadził) wygra, jeśli będzie grać prawidłowo. Mając graf gry N-pozycje i~P-pozycje znajduje się \quotation{indukcją wsteczną}: pozycje końcowe to P-pozycje, pozycje, z~których można dojść jednym ruchem do P-pozycji to N-pozycje, zaś pozycje, z~których {\em każdy} ruch prowadzi do N-pozycji to znów P-pozycje (w~szczególności warunek ten spełniają pozycje końcowe!). \stopteacher \startanswer \placefigure[none,middle]{}{% \starttikzpicture[x=2.5cm,y=-2cm] \def\pos#1#2#3#4#5{$(#1,#2,#3)^{#4}$\rlap{\!,\,#5}} \node (112) at (0,0) {\hphantom{\!,\,2}\pos112N2\hphantom{\!,\,2}}; \node (012) at (-1,1) {\pos012N3}; \node (102) at (0,1) {\pos102N3}; \node (111) at (1,1) {\pos111N1}; \node (002) at (-2,2) {\pos002N2}; \node (011) at (-1,2) {\pos011P0}; \node (101) at (1,2) {\pos101P0}; \node (110) at (2,2) {\pos110P0}; \node (001) at (-1,3) {\pos001N1}; \node (010) at (0,3) {\pos010N1}; \node (100) at (1,3) {\pos100N1}; \node (000) at (0,4) {\pos000P0}; \startscope[->] \draw (112) -- (012); \draw (112) -- (102); \draw (112) -- (111); \draw (112) -| (110); \draw (012) -- (002); \draw (012) -- (011); \draw (012) -- (010); \draw (102) -- (002); \draw (102) -- (101); \draw (102) -- (100); \draw (111) -- (011); \draw (111) -- (101); \draw (111) -- (110); \draw (002) -- (001); \draw (002) |- (000); \draw (011) -- (001); \draw (011) -- (010); \draw (101) -- (001); \draw (101) -- (100); \draw (110) -- (010); \draw (110) -- (100); \draw (001) -- (000); \draw (010) -- (000); \draw (100) -- (000); \stopscope \stoptikzpicture} P-pozycje to dokładnie te pozycje, dla których nim-suma liczebności kupek wynosi~\math{0}. \stopanswer \stopitem \startitem Który gracz ma strategię wygrywającą, jeśli początkowe liczebności kupek wynoszą \math{(3,5,9)}? A~\math{(3,5,6)}? (W~jednej z~tych sytuacji pierwszy gracz wygrywa, o~ile będzie grał prawidłowo. Jaki powinien być jego pierwszy ruch? Ile istnieje takich \quotation{wygrywających} ruchów?) \startanswer \math{3\oplus 5\oplus 9=15\ne 0}, więc jest to N-pozycja i~pierwszy gracz wygrywa. Ponieważ \math{3\oplus 5=6}, może wziąć \math{3}~kamienie z~trzeciej kupki (zostawiając na niej~\math{6}; przy okazji widać, że \math{3,5,6} jest P-pozycją i~gracz startujący z~niej przegrywa). Ponieważ \math{3\oplus 9=10>5}, zabranie żadnej liczby kamieni z~drugiej kupki nie pozwala wygrać pierwszemu graczowi; analogicznie jest z~pierwszą kupką (\math{5\oplus 9=12>3}). Zatem jedyny wygrywający ruch to zabranie \math{3}~kamieni z~trzeciej kupki. \stopanswer \stopitem \startitem Wymyślcie kilka wariantów {\em Nima}; sprawdźcie, jak się w~nie gra. \startanswer Można zwiększyć liczbę kupek, wprowadzić minimalną lub maksymalną liczbę kamieni, jakie można zabrać w~jednym ruchu, zmienić warunek wygranej na przeciwny (przegrywa gracz, który weźmie ostatni kamień) i~in. (Jeden z~wariantów {\em Nima}, {\em Wythoff}, jest przedmiotem kolejnego zadania.) \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Wythoff\time{20--30}}] \startsubject[title={Zasady gry}] Gra przebiega podobnie jak {\em Nim}, z~dwiema różnicami: są tylko dwie kupki kamieni, ale oprócz zabrania dowolnej liczby kamieni z~wybranej kupki można też zabrać dowolną liczbę kamieni z~{\em obu} kupek na raz, pod warunkiem, że weźmiemy ich {\em tyle samo} z~każdej z~nich. \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Rozegrajcie kilka partii (dla różnych liczebności początkowych kupek). Jakimi wynikami może się zakończyć {\em Wythoff}? \startanswer Wygraną któregoś z~graczy\ppauza remis jest niemożliwy. \stopanswer \stopitem \startitem[2] Znajdźcie przykładowe P-pozycje i N-pozycje. \startanswer Przykładowe P-pozycje: \math{(1,2)}, \math{(3,5)}. Przykładowe N-pozycje: \math{(0,n)}, \math{(n,n)}, \math{(1,966)}. \stopanswer \stopitem \startitem[3] Rozważmy następującą grę. Na pewnym polu szachownicy ustawiamy pionek. W~każdym ruchu można przesunąć go o~dowolną liczbę pól w~dół, w~lewo bądź ukosem w~lewo-dół. Zauważcie, że gra ta w~istocie nie różni się od {\em Wythoffa}. \stopitem \startitem Naszkicujcie graf {\em Wythoffa} dla gry rozpoczynającej się od kupek liczących \math{1} i~\math{2} kamieni. \startanswer \starttikzpicture[x=3cm,y=1cm,baseline=(01.base)]%{($(0,1)-(0,.5ex)$)}] \def\pos#1#2#3{\math{(#1,#2)^{#3}}} \node (00) at (0,0) {\pos00P}; \node (10) at (1,0) {\pos10N}; \node (20) at (2,0) {\pos20N}; \node (01) at (0,1) {\pos01N}; \node (11) at (1,1) {\pos11N}; \node (21) at (2,1) {\pos21P}; \startscope[->] \draw (21) -- (11); \draw (21) -- +(0,.5) -| (01); \draw (21) -- (10); \draw (21) -- (20); \draw (11) -- (01); \draw (11) -- (00); \draw (11) -- (10); \draw (01) -- (00); \draw (20) -- (10); \draw (20) -- +(0,-.5) -| (00); \draw (10) -- (00); \stopscope \stoptikzpicture \stopanswer \stopitem \startitem Opiszcie układy początkowe, które gwarantują wygraną II~graczowi (czyli P-pozycje). \startanswer Uwaga: poniższe rozumowanie lepiej widać na obrazku (odręcznie). Oprócz tych wymienionych w~odpowiedzi do \in{punktu}{.}[2], układy takie to m.in. \math{(4,7)}, \math{(6,10)} itd. Każdy taki układ powstaje z~poprzedniego w~następujący sposób: bierzemy najmniejszą liczbę naturalną~\math{n_1}, która dotąd nie wystąpiła w~żadnym układzie\ppauza będzie to liczba kamieni w~mniejszej kupce; w~większej kupce będzie \math{n_2=n_1+d} kamieni, gdzie różnica~\math{d} jest o~jeden większa niż różnica liczebności kupek w~poprzednim układzie. Takie pary liczb mają odpowiednie własności. Po pierwsze, nie można (zabierając kamienie zgodnie z~zasadami) przejść od żadnego z~tych układów do żadnego z~poprzednich: ponieważ każda liczba naturalna występuje wśród opisanych układów dokładnie raz (dlaczego?), zabierając kamienie z~{\em jednej} kupki nie jesteśmy w~stanie przejść do jednego z~poprzednich układów; ponieważ zaś {\em różnice} również się nie powtarzają, zabierając kamienie z~{\em obu} kupek również nie dojdziemy do żadnego z~poprzednich układów. Po drugie, jeśli startujemy z~układu innego niż któryś z~powstałych w~opisany sposób, zawsze możemy dojść do któregoś z~nich; najłatwiej zobaczyć to rysując je na szachownicy i~korzystając z~wersji {\em Wythoffa} opisanej w~\in{punkcie}[3]. Własności te powodują, że każdy z~opisanych układów prowadzi do wygranej gracza, którego ruch akurat przypada, a~każdy inny układ do jego przegranej. \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Hex\time{15--20}}] \startsubject[title={Zasady gry}] Gra toczy się na planszy w~kształcie rombu złożonej z~pól w~kształcie sześciokątów foremnych; boki rombu są oznaczone kolorem białym bądź czarnym tak, że przeciwległe boki mają ten sam kolor. Gracze na przemian zagrywają swoje piony (gracz~I białe, gracz~II czarne) na tych polach; raz położony na planszy pion pozostaje w~tym samym miejscu do końca gry. Wygrywa ten z~graczy, który połączy boki rombu w~\quotation{swoim} kolorze łańcuchem swoich pionów (tj. ciągiem pionów leżących na polach stykających się bokami). \def\hexboard#1#2{% \coordinate (w) at (1,0); \coordinate (e) at ($(2,0)+#1*(3,0)$); \coordinate (n) at ($(0,1.155)+(1.5,-0.866)+#1*(1.5,0.866)$); \coordinate (s) at ($(0,-1.155)+(1.5,0.866)+#1*(1.5,-0.866)$); \coordinate (c) at ($(1.5,0)+#1*(1.5,0)$); \filldraw[fill=black!40] (w) -- (c) -- (n) -- cycle; \filldraw[fill=black!40] (s) -- (c) -- (e) -- cycle; \filldraw[fill=white] (w) -- (c) -- (s) -- cycle; \filldraw[fill=white] (n) -- (c) -- (e) -- cycle; \foreach \ROW in {1,...,#1} \foreach \COL in {1,...,#1} { \filldraw[fill=white, shift={($\ROW*(30:1.732)+\COL*(-30:1.732)$)}] (0:1) -- (60:1) -- (120:1) -- (180:1) -- (240:1) -- (300:1) -- cycle; } \foreach \ROW in {1,...,#1} \node at ($\ROW*(30:1.732)+(-30:1.732)+(150:1.732)$) {\switchtobodyfont[#2]\Characters{\ROW}}; \foreach \COL in {1,...,#1} \node at ($\COL*(-30:1.732)+(30:1.732)+(-150:1.732)$) {\switchtobodyfont[#2]\COL}; } \placefigure[none,middle]{}{% \starttikzpicture[scale=0.5] \hexboard{5}{6pt} \stoptikzpicture} \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Rozegrajcie kilka partii na planszach różnych wymiarów (\math{2\times 2}, \math{3\times 3}, \math{4\times 4}, \math{5\times 5}). Który gracz ma strategię wygrywającą na małych planszach? \stopitem \startitem Jakimi wynikami może skończyć się {\em Hex}? \startanswer Wygraną któregoś z~graczy\ppauza remis jest niemożliwy. \stopanswer \stopitem \startitem Udowodnijcie, że pierwszy gracz ma strategię wygrywającą na planszy dowolnego rozmiaru. \startanswer Można zastosować rozumowanie zwane {\em kradzieżą strategii}. Gdyby to {\em drugi gracz} miał strategię wygrywającą (czyli miał {\em optymalną} odpowiedź na każdy ruch pierwszego, prowadzący do wygranej), pierwszy gracz mógłby zrobić pierwszy ruch dowolnie, a~potem \quotation{zapomnieć} o~nim i~traktować odpowiedź drugiego jako \quotation{pierwszy} ruch i~stosować wygrywającą strategię (jako \quotation{drugi} gracz). Gdyby strategia ta wymagała postawienia pionu tam, gdzie gracz ten już postawił swój pion (np. w~pierwszym ruchu), można postawić pion gdziekolwiek. Ponieważ stojący gdzieś pion pierwszego gracza w~niczym nie może {\em pogorszyć} jego sytuacji, opisane postępowanie prowadzi do wygranej pierwszego gracza, wbrew założeniu, że to drugi ma strategię wygrywającą. \stopanswer \stopitem \startitem Który gracz ma strategię wygrywającą na planszy \math{3\times 3}, jeśli białe nie mogą w~pierwszym ruchu zagrać na środku planszy? \startteacher Zadanie otwarte, do dyskusji/eksperymentów. \stopteacher \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Zakreśl do piętnastu\time{15--20}}] \startsubject[title={Zasady gry}] Wypisujemy na kartce liczby od~\math{1} do~\math{9}. Gracze na przemian zakreślają liczbę (każdy swoim kolorem). Gracz, który jako pierwszy wśród \quotation{swoich} liczb będzie miał trójkę liczb, których suma wynosi~\math{15}, wygrywa. \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Jakimi wynikami może zakończyć się gra? \startanswer Wygraną jednego z~graczy lub remisem. \stopanswer \stopitem \startitem Rozegrajcie kilka\ppauza kilkanaście gier. Czy pierwszy gracz może zawsze wygrać? A~drugi? \startanswer Nie, gdy obaj gracze grają optymalnie, gra kończy się remisem. (Optymalną strategię zobaczymy za chwilę.) \stopanswer \stopitem \startitem Wypiszcie wszystkie trójki liczb ze zbioru \math{\{1,2,\dots,9\}}, które sumują się do~\math{15}. Jak wypisać je \quotation{po kolei}, czyli tak, by żadnej nie pominąć i~żadnej nie wypisać więcej niż jeden raz? Ile ich jest? Które liczby ile razy występują w~tych trójkach? \startanswer \math{(1,5,9)}, \math{(1,6,8)}, \math{(2,4,9)}, \math{(2,5,8)}, \math{(2,6,7)}, \math{(3,4,8)}, \math{(3,5,7)}, \math{(4,5,6)}. Każda trójka wypisana jest rosnąco i~wypisane są w~porządku leksykograficznym. Trójek jest \math{8}, a~poszczególne liczby występują w~nich: \math{5} czterokrotnie, \math{2,4,6,8} trzykrotnie, \math{1,3,7,9} dwukrotnie. \stopanswer \stopitem \startitem Jak ułożyć liczby od \math{1} do~\math{9}, żeby było łatwiej grać, tj. żeby trójki sumujące się do~\math{15} były \quotation{dobrze widoczne}? \startanswer Ułożenie ich np. w~następującym {\em kwadracie magicznym} \starttabulate[|c|c|c|][before={},after={}] \NC 2 \NC 9 \NC 4 \NC\NR \NC 7 \NC 5 \NC 3 \NC\NR \NC 6 \NC 1 \NC 8 \NC\NR \stoptabulate pokazuje, że rozważana gra jest to po prostu {\em Kółko i~krzyżyk} w~przebraniu. \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Kółko i~krzyżyk\time{15--20}}] \startsubject[title={Zasady gry}] Znane każdemu (?). \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Jakie są możliwe wyniki w~grze w~{\em Kółko i~krzyżyk}? \startanswer Wygrana jednego z~graczy lub remis. \stopanswer \stopitem \startitem Narysujcie dwa początkowe poziomy drzewa gry. Narysujcie jedną lub dwie gałęzie aż do zakończenia gry. \startanswer (odręcznie) \stopanswer \stopitem \startitem Oszacujcie liczbę możliwych rozgrywek w~{\em Kółko i~krzyżyk}. \startanswer \startitemize[a,packed][stopper=)] \startitem Prostym ograniczeniem górnym jest \math{9!=362\,880}. \stopitem \startitem Jeśli wziąć pod uwagę symetrie w~początkowych dwóch ruchach (w~późniejszych ruchach staje się to bardziej skomplikowane), można postępować następująco. Pierwszy ruch można wykonać na \math{3} sposoby (środek, róg, bok). Jeśli pierwszy ruch był w~środku, drugi ruch może zostać wykonany na \math{2} sposoby; jeśli w~rogu lub na boku, na \math{5} sposobów. Zatem pierwsze dwa ruchy można wykonać na \math{1\cdot 2+2\cdot 5=12} sposobów, a~pozostałe siedem na nie więcej niż \math{7!=5040} sposobów; zatem wszystkich gier może być najwyżej \math{12\cdot 7!=60\,480}. \stopitem \startitem Jeśli wziąć pod uwagę symetrie do trzeciego ruchu, analogiczne rozumowanie pokazuje, że liczba możliwych rozgrywek nie przekracza \startformula (2\cdot4+2\cdot4+3\cdot7)\cdot 6!=30\,960. \stopformula \stopitem \startitem Powyższa analiza nie bierze pod uwagę ani możliwych symetrii w~dalszych ruchach, ani tego, że niektóre gry kończą się przed zapełnieniem planszy. W~2002 roku obliczono, że dokładna liczba rozgrywek w~{\em kółko i~krzyżyk} wynosi \math{26\,830}. \stopitem \stopitemize \stopanswer \stopitem \startitem Rozegrajcie kilka gier. Co powinien zrobić pierwszy gracz? Jaki ruch pierwszego gracza {\em gwarantuje} mu wygraną, niezależnie od tego, jak gra drugi gracz? A~jaki {\em gwarantuje} przegraną, jeśli drugi gracz gra optymalnie? \startanswer Obojętnie, co zrobi pierwszy gracz w~pierwszym ruchu, jeśli w~dalszym ciągu będzie grał optymalnie, nie przegra; jednak żaden ruch nie gwarantuje mu wygranej. (Nie będziemy tego rozpisywać/dowodzić.) \stopanswer \stopitem \startitem Jak wygląda macierz gry w~{\em Kółko i~krzyżyk}? \startanswer \quotation{Strategiami} każdego z~graczy będą funkcje, które każdej {\em sytuacji} na planszy przyporządkowują {\em ruch}. Oczywiście, różne układy strategii I i~II gracza będą prowadzić do różnych wyników gry. \stopanswer \stopitem % \startitem % Opiszcie własności gry w~kółko i~krzyżyk. % \startanswer % Jest dwóch graczy; gracze wykonują ruchy kolejno, a~nie % jednocześnie (chyba, że przez \quotation{ruch} będziemy % rozumieć \quotation{wybór strategii} (w~sensie poprzedniego % zadania)); gracze dysponują pełną informacją; gra kończy się % po skończenie wielu ruchach (maksymalnie dziewięciu); % \stopanswer % \stopitem \startitem Opiszcie optymalną strategię w~{\em Kółko i~krzyżyk} dla I i~II gracza. \startanswer Oto przykładowy zapis strategii optymalnej (co ciekawe, działający dla każdego gracza). W~każdej sytuacji należy sprawdzać, czy kolejne punkty mają zastosowanie, i~jeśli tak, wykonać opisaną w~nich akcję. \startitemize[a,packed][stopper=)] \startitem[a] Jeśli masz dwa symbole w~rzędzie, a~trzecie miejsce jest puste, zakreśl to puste miejsce; {\em wygrywasz}. \stopitem \startitem Jeśli przeciwnik ma dwa symbole w~rzędzie, a~trzecie miejsce jest puste, zakreśl to puste miejsce. \stopitem \startitem Jeśli możesz, stwórz {\em zagrożenie}, czyli sytuację, w~której masz {\em dwa} rzędy z~dwoma swoimi symbolami i~trzecim pustym miejscem. \stopitem \startitem Jeśli w~następnym ruchu przeciwnik będzie w~stanie utworzyć {\em zagrożenie}, utwórz sytuację opisaną w~\in{punkcie}{)}[a]. \stopitem \startitem Jeśli środek jest wolny, zagraj w~nim. \stopitem \startitem Jeśli przeciwnik zagrał w~narożniku i~przeciwległy narożnik jest wolny, zagraj w~nim. \stopitem \startitem Jeśli którykolwiek narożnik jest wolny, zagraj w~nim. \stopitem \startitem Zagraj gdziekolwiek. \stopitem \stopitemize \stopanswer \stopitem \startitem Wymyślcie kilka wariantów {\em Kółka i~krzyżyka}. \startanswer Do znanych wariantów należą np. {\em Kółko i~krzyżyk} na planszy \math{4\times 4} (do wygranej trzeba mieć \math{4} swoje symbole w~wierszu, kolumnie lub na przekątnej), {\em gomoku} (do wygranej trzeba mieć \math{5} symboli, plansza ma rozmiar \math{19\times19}), {\em Kółko i~krzyżyk} trójwymiarowe (i~w~wyższych wymiarach), {\em Anty-kółko i~krzyżyk}, gdzie gracz, który ma trzy symbole w~rzędzie, przegrywa, {\em kwantowe Kółko i~krzyżyk} i~wiele innych. \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Kiełki\time{10--15}}] \startsubject[title={Zasady gry}] Na kartce rysujemy cztery kropki (lub inną ich liczbę). Gracze wykonują ruchy na przemian. Ruch polega na połączeniu dwóch wybranych kropek linią i~narysowaniu na tej linii (ale nie na żadnym z~końców) kolejnej kropki, przy czym należy przestrzegać następujących dwóch zasad: \startitemize[r,text][stopper=] \startitem linie nie mogą się przecinać, \stopitem \startitem[kielki2] z~jednej kropki mogą wychodzić co najwyżej trzy linie. \stopitem \stopitemize Gracz, który nie może wykonać ruchu zgodnie z~tymi zasadami, przegrywa. \stopsubject \startsubject[title={Zadania}] \startexercises \startitem Rozegrajcie kilka partii. Czy potraficie grać tak, żeby gra się {\em nie} skończyła? \stopitem \startitem Udowodnijcie, że gra w~{\em Kiełki} zawsze kończy się po skończenie wielu ruchach. \startanswer Na początku jest \math{4\times 3=12} możliwych końców linii, bo z~każdej z~\math{4} kropek mogą wychodzić maksymalnie~\math{3} linie. W~każdym ruchu, rysując linię, zmniejszamy tę liczbę o~\math{2} (\quotation{wykorzystujemy} dwa możliwe końce) i~zwiększamy o~\math{1} (bo dorysowana kropka może być końcem tylko dla jednej linii, zgodnie z~\in{zasadą}[kielki2]). \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startchapter[title={Gry w~kości\time{10--20}}] \startexercises \startitem Rozważmy następującą grę. Rzucamy kością (symetryczną, sześcienną), po czym, jeśli chcemy, rzucamy ponownie (ale najwyżej raz). \startitemize[a,packed][stopper=)] \startitem Jak będzie wyglądała macierz tej gry? \startanswer W~wierszach będą znajdować się {\em strategie gracza}, czyli \quotation{przepisy} określające sposób postępowania (tj. czy przerzucamy kość czy nie) dla każdego wyniku pierwszego rzutu. W~kolumnach będą znajdować się {\em strategie przyrody}, czyli wyniki dwóch kolejnych rzutów kością. \stopanswer \stopitem \startitem Ile jest możliwych strategii gracza, a~ile przyrody w~tej grze? \startanswer Gracz ma \math{2^6=64} strategie: dla każdego z~sześciu możliwych wyników niezależnie określamy, czy przerzucamy kość, czy nie (zasada mnożenia lub wariacje z~powtórzeniami\ppauza sześć razy wybieramy niezależnie jedną z~dwóch możliwości). Przyroda ma \math{6^2=36} strategii. \stopanswer \stopitem \startitem Rozważmy następującą strategię: \quotation{jeśli wypadnie \math{k} lub mniej oczek, przerzucamy kość, w~przeciwnym wypadku pozostajemy przy wyniki pierwszego rzutu}. Jakie powinno być \math{k}, aby wartość oczekiwana wyniku była największa? \startanswer Wartość oczekiwana wynosi \startformula k(\tfrac{1}{6^2}1+\cdots+\tfrac{1}{6^2}6) +\bigl(\tfrac{1}{6}(k+1)+\cdots+\tfrac{1}{6}6\bigr) =\tfrac{1}{12}(-k^2+6k+42), \stopformula a~więc osiąga maksimum dla \math{k_{\rm max}=3}. \stopanswer \stopitem \stopitemize \stopitem \startitem Rozważmy podobną grę, w~której można przerzucić kość co najwyżej dwa razy. \startitemize[a,packed][stopper=)] \startitem Ile jest możliwych strategii gracza w~tej grze? \startanswer Po pierwszym rzucie mamy tym razem nie dwie możliwości (pozostanie bądź przerzucenie), ale \math{1+2^6} możliwości: pozostanie (jeden sposób) bądź kontynuacja (\math{2^6} sposobów na mocy poprzedniego zadania). Ponieważ dalsze postępowanie określamy niezależnie dla każdego z~sześciu wyników, analogicznie jak poprzednio mamy \startformula (1+2^6)^6=75\,418\,890\,625 \stopformula możliwych strategii. \stopanswer \stopitem \startitem Która strategia jest korzystniejsza (daje większą wartość oczekiwaną): \quotation{rzucamy tak długo, aż wypadnie więcej niż \math{3} oczka, ale nie więcej niż trzy razy}, czy \quotation{jeśli w~pierwszym rzucie wypadła szóstka, pozostajemy przy tym wyniku, w~przeciwnym przypadku rzucamy drugi raz; jeśli wówczas wypadnie więcej niż trzy oczka, pozostajemy przy tym wyniku, a~jeśli nie, rzucamy po raz ostatni}? \startanswer Pierwsza strategia daje wartość oczekiwaną \math{4\frac{5}{8}=4{,}625}, zaś druga \math{4\frac{13}{24}\approx 4{,}542}. \stopanswer \stopitem \stopitemize \stopitem \startitem Rozważmy następującą grę: rzucamy parą kości, po czym możemy raz przerzucić jedną, drugą lub obie kości. Wynikiem jest suma oczek na obu kościach, chyba, że wypadły dwie szóstki, wówczas wynik wynosi zero. Jaką zaproponowalibyście strategię w~tej grze? \startanswer Pytanie otwarte, nie jesteśmy w~stanie łatwo wyliczyć strategii maksymalizującej wartość oczekiwaną wyniku w~tej grze. Warto przedyskutować kilka problemów związanych z~tą grą, np. liczbę możliwych strategii (można przyjąć, że kości są rozróżnialne lub nie!), sposób postępowania, gdy wypadnie jedna szóstka (np. gdy przerzucimy tylko drugą kość, wartość oczekiwana wyniesie \startformula \tfrac{1}{6}(6+1)+\cdots+\tfrac{1}{6}(6+5)+\tfrac{1}{6}\cdot0 =7\tfrac{1}{2}\text{,} \stopformula więc jeśli na drugiej kości wypadło więcej niż~\math{1}, nie warto jej przerzucać), wariant, w~którym za dwie szóstki otrzymujemy \math{-6} punktów. \stopanswer \stopitem \stopexercises \stopchapter \startchapter[title={Projektowanie własnej gry\time{reszta czasu, \hskip 0pt plus 4em\penalty20\hskip 0pt plus -4em\relax 20--60}}] \startsubject[title={Początkowe zasady gry}] Gracze są właścicielami fabryk znajdujących się nad rzeką. Produkcja jest związana z~powstawaniem odpadów, które właściciele wylewają do rzeki. Gdy poziom zanieczyszczeń okaże się zbyt duży, następuje kontrola i~wszystkie fabryki zostają zamknięte. Wygrywa ten, który zdołał do tego momentu wyprodukować najwięcej (zarobić najwięcej pieniędzy). We wspólnej puli kładziemy kamienie (patyczki, sztony...) w~liczbie dziesięciokrotnie większej od liczby graczy. Gracze kolejno rzucają kostką. Po rzucie każdy gracz zabiera tyle kamieni, ile wyrzucił oczek. Gdy kamienie się skończą, wygrywa gracz, który zebrał ich najwięcej. \stopsubject \startsubject[title={Zadania}] \startexercises[2*broad] \startitem Wymyślcie tytuł dla tej gry. \stopitem \startitem Powyższe zasady zawierają pewną niejasność. Znajdźcie ją. \startanswer Nie wiadomo, co zrobić, gdy gracz kończący grę ma wziąć {\em więcej} kamieni, niż pozostało w~puli: czy powinien wziąć tyle, ile ich tam jest, czy wpierw uzupełnić pulę odpowiednią liczbą kamieni i~wziąć tyle, ile wskazuje kostka. \stopanswer \stopitem \startitem Czy ta gra zawsze się skończy? Jaka jest minimalna, średnia i~maksymalna liczba ruchów? \startanswer Tak\ppauza jest skończenie wiele kamieni, w~każdym ruchu zabiera się co najmniej jeden. Najmniej ruchów będzie, gdy wszyscy będą wyrzucali szóstki: \math{\lceiling 10n/6\rceiling}, gdzie \math{n} to liczba graczy. Najwięcej ruchów (\math{10n}) będzie, gdy wszyscy będą wyrzucali jedynki. Średnio będzie \math{\lceiling 10n/3{,}5\rceiling} ruchów. \stopanswer \stopitem \startitem Powyżej opisana gra jest bardzo nudna. Dlaczego? \startanswer Ponieważ gracze nie podejmują żadnych decyzji, wszystko rozstrzygają rzuty kośćmi. \stopanswer \stopitem \startitem Jak można ulepszyć tę grę? \startanswer Oto (otwarta) lista pomysłów (niektóre z~nich są {\em złe}, ale niech uczniowie sami do tego dojdą!). Warto zwrócić uwagę, że {\em dobry} pomysł oznacza nie tylko, że gra staje się interesująca (trzeba podejmować niełatwe decyzje, zdarzają się nieoczekiwane zwroty akcji itp.), ale też ma uzsadanienie w~fabule gry. Każdy pomysł wymaga też sprawdzenia\ppauza przetestowania na kilku (w~rzeczywistości kilkudziesięciu czy kilkuset) rozgrywkach i~ewentualnej modyfikacji (a~czasem porzucenia). \startitemize[packed] \startitem Zmiana liczby kamieni. \stopitem \startitem Zmiana liczby kości (np. każdy gracz rzuca trzema kośćmi). \stopitem \startitem Możliwość kilkukrotnego (np. trzykrotnego) powtórzenia rzutu wybranymi kośćmi. \stopitem \startitem Zabieranie kamieni w~innej liczbie niż wynik na kostce (lub suma wyników): można rozważyć iloczyn, kwadrat lub pierwiastek sumy, sumę różnic między wynikami lub jeszcze inną funkcję. (Niektóre funkcje nadają się do tego kiepsko, np. kwadrat sumy prowadzi do dość dużych liczb, co jest niewygodne.) \stopitem \startitem Wprowadzenie układów {\em bonusowych}, np. dwa lub trzy identyczne wyniki lub trzy kolejne liczby naturalne na kostkach mogą dać efekt specjalny (np. odebranie zebranych kamieni \ppauza w~ustalonej liczbie, np. zależnej od liczby oczek\ppauza innym graczom, zmuszenie innych graczy do oddania kamieni do puli i~in.) \stopitem \startitem Wprowadzenie układów {\em malusowych}, np. każda szóstka może oznaczać konieczność oddania do puli lub innym graczom pewnej liczby kamieni itp. \stopitem \startitem Gracze mogą wykonywać ruchy równocześnie zamiast kolejno. (Trzeba ustalić, jak wtedy postępować, jeśli w~trakcie ruchu skończą się kamienie w~puli, oraz jakie dokładnie informacje są jawne dla pozostałych graczy w~czasie ruchu.) \stopitem \startitem Można zmienić warunki zwycięstwa, np. wygrywać może gracz, który zebrał najwięcej kamieni, ale z~wyłączeniem tego, który spowodował wyczerpanie puli. \stopitem \startitem Przy jednym rodzaju kamieni zarobione pieniądze i~usunięte zanieczyszczenia wyrażają się tą samą liczbą. Można wprowadzić dwa rodzaje kamieni i~zróżnicować te liczby, ustalając, że np. \math{n} zanieczyszczeń jest związane z~zarobieniem \math{n^2}, \math{\sqrt{n}} lub inną ilością pieniędzy. \stopitem \stopitemize \stopanswer \stopitem \stopexercises \stopsubject \stopchapter \startnotmode[nauczyciel] \page \setuppagenumber[state=stop] \midaligned{% \starttikzpicture[scale=1.8,rotate=-30] \hexboard{2}{10pt} \stoptikzpicture } \par\blank[6*big] \midaligned{% \starttikzpicture[scale=1.8,rotate=-30] \hexboard{3}{10pt} \stoptikzpicture } \page \midaligned{% \starttikzpicture[scale=1.8,rotate=60] \hexboard{4}{10pt} \stoptikzpicture } \page \centerbox{% \starttikzpicture[scale=1.8,rotate=60] \hexboard{5}{10pt} \stoptikzpicture } \stopnotmode \stoptext