Gra w marynarza – dalsze własności

Gra w marynarza wraca do łask. Po tym jak wcisnąłem się na pewną konferencję ze swoim referatem dotyczącym właśnie gry w marynarza (XVII Międzynarodowe Warsztaty dla Młodych Matematyków „Matematyka Dyskretna”), zachorowałem ponownie na „chorobę morską”. :) Po wygłoszeniu referatu otrzymałem jedno, ale bardzo dobre pytanie, o to czy rozważałem jakieś symetrie między graczami. Chociaż w pierwszej chwili nie dotarło do mnie w ogóle,  o co ta osoba pytała, zainspirowało mnie do otrzymania nowych rezultatów, które dziś zamierzam przedstawić. Odpowiadając na pytanie: jakoś szczególnie rozważać, nie rozważałem, ale w niektórych przypadkach gracze o przeciwnych numerach (później sprecyzujemy to pojęcie) mieli takie same szanse na wygraną w grze. Rzeczywiście przy pewnych dosyć naturalnych warunkach tak się dzieje, udało mi się je ustalić i znaleźć uzasadnienie.

Pozwolę sobie teraz na skrótowe przypomnienie dotyczące gry w marynarza a Czytelników, dla których będzie ono niewystarczające odsyłam do mojego wpisu Gra w marynarza. Natomiast Czytelników zainteresowanych nowościami odsyłam do momentu wpisu, gdy pojawia się warunek konieczny.

Model gry jest następujący. Powiedzmy, że w grze uczestniczy m graczy, numerowanych: 0,1, \dots m-1; każdy z nich wybiera liczbę z pewnego, wspólnego dla wszystkich zakresu Z \subset \mathbb{Z}. Jeśli x_1, x_2, \dots x_m \in Z są liczbami wybranymi przez graczy w danej rozgrywce to sumujemy je S:=x_1+ x_2+ \dots + x_m i zwycięzcą jest gracz o numerze, który jest resztą z dzielenia sumy S przez liczbę gracz m: r_m(S). Dodatkowo będziemy rozważać tylko model gry z klasyczną definicją prawdopodobieństwa, tzn. po pierwsze zakres liczb jest skończony: \# Z< \infty. Po drugie, przyjmując przestrzeń zdarzeń elementarnych

\Omega:=\{ ( x_1, x_2, \dots x_m): x_i \in Z \}=Z^m

definiujemy prawdopodobieństwo dla dowolnego A \subset \Omega wzorem:

P(A):=\frac{\# A}{\# \Omega}.

Aby móc badać szanse graczy na wygraną, potrzeba jeszcze opisać zbiory zdarzeń sprzyjających wyborowi każdego z graczy. Dlatego dla gracza o numerze k, definiujemy:

\displaystyle W_k:=\{( x_1, x_2, \dots x_m) \in \Omega: r_m(x_1+ x_2+ \dots + x_m)=k\}.

Powyższy warunek możemy jeszcze zapisać jako

x_1+ x_2+ \dots + x_m \equiv k \mod m

lub

x_1+_m x_2+_m \dots +_m x_m=k, gdzie +_m jest dodawaniem modulo m.

Jeśli każdy z graczy ma równe szanse, to oczywiście dla każdego k \in \{0,1, \dots m-1 \}=\mathbb{Z}_m zachodzi równość

P(W_k)=\frac{1}{m}

Czyli np.

m \cdot \#W_k =\# \Omega

A z tego wniosek, że

m|\# \Omega (warunek konieczny)

Przypomnijmy, że \# \Omega=\# (Z^m)= (\# Z)^m. Zatem dalsze implikacje warunku koniecznego są takie, że dla każdej liczby pierwszej p \in \mathcal{P}, dla której

p|m

mamy również p| (\#Z)^m, a więc

p| \# Z.

Zatem wszystkie liczby pierwsze występujące w rozkładzie liczby graczy m występują również w rozkładzie liczby elementów zakresu \# Z. W szczególności, gdy m jest liczbą pierwszą, to \#Z jest wielokrotnością m. Działa to też dla liczb złożonych postaci p_1 p_2 \cdot \dots \cdot p_n dla pewnych różnych liczb pierwszych p_i. Problem pojawia się gdy w rozkładzie m występują liczby pierwsze w potędze wyższej niż pierwsza.

Zostało już pokazane np. że dla zakresów postaci Z=\{0,1, \dots n \} gracze mają równe szanse, gdy m| \# Z. Można postawić hipotezę(1), że w żadnym innym przypadku szanse nie będę równe. Dzieje się tak dla zakresów tej postaci, gdy liczba graczy jest pierwsza. Problem pozostaje nierozwiązany w pozostałych przypadkach.

Kolejna hipoteza(2) jaką stawiam jest taka, że dla Z \subset \mathbb{Z}_m jedynym zakresem liczb, który daje równe szanse będzie Z=\mathbb{Z}_m. Czyli że \mathbb{Z}_m jest minimalnym dobry zakresem (że jest dobrym już pokazałem). Pokażę teraz warunek wystarczający na równe szanse na wygraną dwóch konkretnych graczy, który nieco nawiązuje do tej hipotezy jak i do pytania zadanego na konferencji.

Twierdzenie 1.

Zakładamy cały czas, że w grze jest m graczy. Niech zakres Z będzie podgrupą (\mathbb{Z}_m, +_m) a dla graczy o numerach k,l zachodzi l-k\in Z (w sensie odejmowania modulo m). Wtedy gracze k,l mają równe szanse.

Dowód. Potrzebujemy wykazać, że \# W_k = \# W_l. W tym celu zdefiniujemy funkcję

f: W_k \ni (x_1, x_2, \dots x_m) \mapsto (x_1+_m r, x_2, \dots x_m) \in W_l

gdzie r:=l-k. Po pierwsze uzasadnimy poprawną określoność. Niech (x_1, x_2, \dots x_m) \in W_k. Wtedy

\displaystyle \sum_{i=1}^m x_i \equiv k \mod m

A stąd

\displaystyle \sum_{i=1}^m x_i +r\equiv k +l-k \mod m oraz k+l-k=l.

Ponadto założyliśmy, że r \in Z oczywiście x_1 jako liczba wybrana przez jednego z graczy też należy do Z. Ponieważ Z jest podgrupą, więc x_1+_m r \in Z. Zatem rzeczywiście (x_1+_m r, x_2, \dots x_m) \in W_l.

Teraz możemy przejść do dowodu różnowartościowości. Jeśli f(x_1, \dots x_m)=f(y_1, \dots y_m), to zgodnie z definicją f mamy x_i=y_i dla i>1 oraz x_1+_m r=y_1+_m r. Zatem skreślając po obu stronach równania r otrzymujemy również x_1=y_1. Co pokazuje ostatecznie, że (x_1, \dots x_m)=(y_1, \dots y_m).

Teraz dla dowodu surjektywności weźmy (y_1, \dots y_m) \in W_l. Połóżmy (x_1, x_2, \dots x_m):=(y_1 +_m (-r), y_2, \dots y_m).  Stosując to samo rozumowanie co wcześniej zauważamy, że

\displaystyle \sum_{i=1}^n y_i -r \equiv l -(k-l) \mod m.

Ponadto z faktu, że Z jest podgrupą oraz y_1 ,r \in Z wynika, że -r \in Z a więc także y_1 +_m (-r) \in Z. Zatem ostatecznie (x_1, x_2, \dots x_m) \in W_k oraz w sposób oczywisty f(x_1, x_2 \dots x_m)=(y_1, y_2 \dots y_m). QED

Wydaje się, że fajne kryterium i z być może ciekawym zastosowaniem w rzeczywistości. Jednak podgrupy, jako zakresy liczb, mają jednak specyficzną własność.

Wniosek 1.

Jeżeli  zakres liczb Z jest podgrupą \mathbb{Z}_m, to wszyscy gracze którzy należą do Z mają równe (i dodatnie) szanse na wygraną, a wszyscy pozostali gracze nie mają w ogóle szans na wygraną (mają zerowe szanse).

Dowód.

Załóżmy k \in Z. Wtedy  k-0 \in Z. Zatem stosując Twierdzenie 1. otrzymujemy \# W_k=\# W_0. Zatem z dowolności k dostajemy pierwszą część tezy.

Teraz niech k \notin Z. Przypuśćmy, że jednak k ma dodatnie szanse na zostanie wybranym, a więc istnieją x_1,x_2, \dots x_m \in Z takie, że x_1+_m x_2+_m \dots +_m x_m=k, ale Z jest podgrupą, co implikuje k \in Z – sprzeczność. QED

Oczywiście w przypadku podgrup zawsze zachodzi 0 \in Z. Zatem rzeczywiście gracze z Z mają takie same dodatnie prawdopodobieństwo wygranej, a gracze spoza Z mają szanse zerowe. W szczególności prawdopodobieństwo wygranej dla gracza z Z wynosi \frac{1}{\# Z}.

Ten wniosek uwidacznia słabostkę podgrup, gdy nie są pełne, nie wszyscy gracze są w ogóle osiągalni. Ponadto, by zastosować ten trick w rzeczywistości, np. w celu ustawienia wyników jakiegoś losowania przy pomocy marynarza, trzeba by mieć do czynienia z osobami o sporej naiwności matematycznej, Np. w przypadku ośmiu graczy i najliczniejszej podgrupy \{0,2, 4,6\} na pierwszy rzut oka widać, że gracze o numerach nieparzystych nie mają szans na zostanie wybranymi. Można oczywiście próbować szukać bardziej zawiłych przykładów, ale wątpię, aby ktoś dał się nabrać.

Chciałem też dodać, że kryterium, którego dostarcza Twierdzenie 1. nie tylko mówi, którzy dwaj gracze mają równe szanse, ale determinuje szanse na wygraną dla wszystkich graczy.

Oczywistym wnioskiem, jaki mogliśmy już wcześniej postawić, jest to, że gdy grupa jest pełna, to wszyscy mają równe szanse na wygraną.

Wniosek 2.

Jeśli Z=\mathbb{Z}_m, to wszyscy gracze mają równe szanse.

Zatem zbiorczo możemy powiedzieć, że

Wniosek 3.

Załóżmy, że zakres Z jest podgrupą \mathbb{Z}_m. W takiej sytuacji: wszyscy gracze mają równe szanse na wygraną wtedy i tylko wtedy, gdy Z=\mathbb{Z}_m.

Jedyna dobra podgrupa, dla której każdy z graczy ma równe szanse na wygraną to podgrupa pełna. Jest to wg mnie kolejna przesłanka przemawiająca za prawdziwością hipotezy(2). W istocie dowodzi ją dla pewnej kategorii zbiorów, jaką są podgrupy.

Teraz obiecane we wstępie twierdzenie, które zachodzi jakby na przekór hipotezie(1).

Definicja 1.

Gdy w grze uczestniczy m graczy: 0,1,\dots m-1, to przez gracza przeciwnego do gracza k rozumiemy liczbę przeciwną do k w \mathbb{Z}_m, czyli m-k, dla k\neq 0 i 0 dla k=0. Dla prostoty będziemy oznaczać ją -k.

W tej części wpisu będziemy zakładać, że zakres jest ciągiem kolejnych liczb naturalnych do jakiegoś n:  Z=\{0,1, \dots n \}. W takiej sytuacji zdefiniujmy pewną funkcję:

\hbox{inv}:Z \ni k \mapsto n-k \in Z

Zauważmy, że \hbox{inv} jest permutacją zbioru Z taką, która odwraca kolejność elementów. W szczególności jest sama do siebie odwrotna. Ma ona także następującą własność odwracania graczy.

Własność (odwracania graczy).

Niech l \in \mathbb{Z}_m oraz (x_1, x_2, \dots x_m) \in W_lWtedy (\hbox{inv}(x_1),\hbox{inv}(x_2), \dots \hbox{inv}(x_m)) \in W_{-l}.

Dowód.

Policzmy wprost sumę odwróconych współrzędnych:

\displaystyle \sum_{i=1}^m \hbox{inv}(x_i)=\sum_{i=1}^m n- x_i=mn-\sum_{i=1}^m x_i \equiv -l \mod m

Biorąc jeszcze pod uwagę fakt, że \hbox{inv}:Z \mapsto Z otrzymujemy tezę. QED

Zwróćmy uwagę, że istotne było jeszcze to, że sumowaliśmy dokładnie m liczb. Jest to więc własność czysto gry w marynarza. Nie zawsze ma to znaczenie,  gdyż np. we wcześniejszych własnościach, gdybyśmy rozważali abstrakcyjne zbiory

\displaystyle W^N_k:=\{(x_1, \dots x_N): x_i \in Z, \sum_{i=1}^N x_i \equiv k \mod m\},

rezultat pozostałby taki sam.

Wracając do obecnej sytuacji, dzięki powyższej własności możemy przystąpić już do dowodu głównego twierdzenia.

Twierdzenie 2.

Jeśli w grze uczestniczy m graczy a zakres jest postaci Z=\{0,1 \dots n\}to każdy gracz ma takie samo prawdopobieństwo wygranej jak gracz przeciwny.

Dowód.

Ustalmy gracza k\in \mathbb{Z}_m. Naszym celem jest wykazanie \# W_k = \#W_{-k}. Zdefiniujemy więc funkcję, która posłuży do uzasadnienia żądanej równoliczności:

\hbox{INV}: W_k \ni (x_1,x_2, \dots ,x_m) \mapsto (\hbox{inv}(x_1),\hbox{inv}(x_2), \dots ,\hbox{inv}(x_m)) \in W_{-k}

Zgodnie z własnością odwracania graczy jest ona poprawnie określona. Różnowartościowość wynika wprost z różnowartościowości \hbox{inv}. Pozostaje jedynie do wykazania surjektywność. Zatem niech (y_1, y_2, \dots y_m) \in W_{-k}. Ponownie korzystając z własności odwracania graczy mamy, że (x_1, x_2, \dots x_m):= (\hbox{inv}(y_1), \hbox{inv}(y_2), \dots \hbox{inv}(y_m)) \in W_k. Dodatkowo z faktu, że  \hbox{inv}=\hbox{inv}^{-1} dostajemy ostatecznie

INV(x_1,x_2 \dots x_m)=(y_1, y_2, \dots y_m).

QED

Twierdzenie pokazuje, że pary graczy o przeciwnych numerach mają równe szanse. Biedny, bo bez pary jest zawsze gracz 0 i gdy m jest parzyste, to \frac{m}{2}. Oczywiście nie wynika z tego, że wszyscy mają równe szanse, ale powoduje, że liczenie prawdopodobieństwa wygranej dla graczy, wystarczy ograniczyć do mniej więcej połowy graczy (przy założeniu normalnego zakresu). Twierdzenie można by też nieco uogólnić. Zakres nie musi być koniecznie postaci Z=\{0,1, \dots n\}, wystarczy, żeby składał się z pewnej liczby kolejnych wyrazów ciągu arytmetycznego. Choć jedyne sensowne są te z różnicą równą jeden, gdyż może wystąpić problem z osiągalnością graczy (jak poprzednio), w ogóle by zapobiegać nieosiągalności graczy dobrym zwyczajem jest używanie zakresu, do którego należą 0,1.

Oszacowanie szansy na wygraną.

W ciągu ostatnich dni zauważyłem, że jeśli założymy zakres odpowiedniej postaci, to można znaleźć oszacowanie na minimalne i maksymalne szanse na wygraną. Przedstawię poniżej dwa twierdzenia.

Twierdzenie 3.

Przy dowolnej liczbie graczy m oraz zakresie Z \subset \mathbb{Z}_m prawdopodobieństwo wygranej dowolnego gracza jest nie większe niż \displaystyle \frac{1}{\# Z}. Dodatkowo, jeśli Z \neq \mathbb{Z}_m, to nierówność jest ostra dla każdego gracza, którego numer możemy uzyskać przez różnicę k-i , gdzie i \in Z a k \in \mathbb{Z}_m \setminus Z.

Dowód.

Ustalmy gracza k \in \mathbb{Z}_m. Definiujemy funkcję:

f_k: W_k \ni (x_1,x_2, \dots x_m) \in (x_2 \dots x_m) \in Z^{m-1}

która każdej m-ce z W_k obcina pierwszą współrzędną.

Dowiedziemy, że f jest różnowartościowa. W tym celu przyrównajmy f_k(x)=f_k(y) na x=(x_1, \dots x_m), y=(y_1, \dots x_m) \in W_k. Z definicji funkcji otrzymujemy automatycznie x_i=y_i dla i\geq 2. Dodatkowo z definicji W_k wynika, że

x_1+_m (x_2 +_m \dots +_m x_m)=k=y_1+_m (y_2 +_m \dots +_m y_m)

ale ponieważ x_i=y_i dla i \geq 2 możemy skreślić te wszystkie czynniki po obu stronach równości, otrzymując x_1=y_1.

Zatem f_k jest różnowartościowa, a stąd \#W_k \leq \#(Z^{m-1})=(\#Z)^{m-1}. Zatem

\displaystyle P(W_k)=\frac{\#W_k}{(\# Z) ^m}\leq \frac{(\# Z) ^{m-1}}{(\#Z) ^m}=\frac{1}{\# Z}.

Dla dowodu drugiej części załóżmy, że Z \neq \mathbb{Z}_m. Weźmy i \in Z oraz k \notin Z.  Zauważmy, że f_{k-i} nie przyjmuje (i, \dots i) \in Z^{m-1}, bo gdyby tak było dla pewnego x \in W_{k-i}, oznaczałoby to, że x_1 +_m (m-1)i=k-i, a stąd x_1=k – sprzeczność, bo k \notin Z. QED

To oszacowanie odnosiło się do hipotezy(2). Teraz oszacowanie oddolne dla sytuacji z hipotezy(1).

Twierdzenie 4.

Załóżmy, że w grze uczestniczy m graczy oraz że dany jest zakres postaci Z=\{0,1 \dots n\}Niech d:=\min \{l \in \mathbb{N}: ln\geq m-1\}. Wtedy prawdopodobieństwo wygranej dowolnego gracza wynosi co najmniej \displaystyle \frac{1}{\# Z ^ d}.

Dowód.

Ustalmy gracza k \in W_k. Zauważmy, że d<m o ile n>0. Możemy zatem zdefiniować funkcję

f: W_k \ni (x_1,x_2, \dots x_m) \in (x_{d+1} \dots x_m) \in Z^{m-d}

która każdej m-ce z W_k obcina d pierwszych współrzędnych.

Tym razem wykażemy, że funkcja ta jest surjekcją. Niech y=(y_{d+1}, \dots y_m) \in Z^{m-d}. Potrzebujemy znaleźć takie y_1, y_2 \dots y_d, że \sum_{i=1}^m y_i=k. Czyli aby y_1 +_m \dots +_m y_d=r, gdzie r=k+_m (-(y_{d+1}+_m \dots +_m y_m))

Ale zauważmy, że \sum_{i=1}^dZ:=\{ \sum_{i=1}^d y_i: y_i \in Z\}=\{0,1, \dots dn\}. A stąd A zawiera \mathbb{Z}_m, gdyż dn \geq m -1. W szczególności r \in \sum_{i=1}^d Z, co oznacza, że znajdziemy y_1, \dots y_d o żądanej własności. QED

Co prawda nie udowodniłem jeszcze żadnej z hipotez, ale mam nadzieję, że ten wpis zawiera wystarczająco dużo nowego materiału, żeby był sens go publikować. :)

Reklamy