Gra w marynarza

Dzisiejszy wpis poświęcony będzie grze w marynarza. Napisałem na ten temat pracę licencjacką, więc głównie przedstawię jej streszczenie, ale dodam też jeden dowód korzystający z własności systemów pozycyjnych jako ciekawe zastosowanie. Streszczenie i ewentualne rozumowania tam prezentowane będą pobieżne, ale dla osób, dla których będą one niewystarczające i w ogóle dla wszystkich zainteresowanych na samym dole umieszczam linka do całości mojej pracy.

Zasady.

Gra w marynarza to prosta i dosyć znana metoda pozwalająca wylosować jedną osobę spośród pewnej grupy (przynajmniej dwuosobowej, żeby losowanie miało sens). Polega ona na tym, że gracze ustawiają się w kole, wyróżniona zostaje jedna osoba (od niej zostanie rozpoczęte odliczanie), następnie każdy z graczy niejawnie wybiera pewną liczbę palców i na umówiony znak, wszyscy ujawniają swoje liczby. Zostają one zsumowane a ich wartość odliczona (zgodnie z ruchem wskazówek zegara) od wybranej na początku osoby. Ostatnia wskazana osoba w odliczaniu zostaje wybrana.

Gra ta nie zawsze daje każdemu z graczy równe szanse na wygraną, ale jednocześnie przy pewnych słabych założeniach można oczekiwać zupełnie sprawiedliwego wyniku.

Odliczanie.

Po pierwsze, łatwo można zauważyć, że efektem odliczania spośród graczy g_0, g_1, \dots g_{n-1} będzie gracz o numerze, który jest resztą z dzielenia sumy S wskazanych liczb przez graczy. Gdyby bowiem podzielić z resztą przez n sumę liczb wybranych przez graczy to otrzymamy S=dn+r i wtedy d będzie liczbą pełnych obrotów jaką wykonamy po kole, czyli operacją, po której wrócimy do punktu od którego zaczynamy odliczanie, natomiast r niepełnym obrotem, czyli właśnie numerem pewnej osoby, na której odliczanie się zakończy. Wykazuję to w sposób formalny w swojej pracy, choć myślę, że takie intuicyjne wyjaśnienie wystarczająco przemawia do wyobraźni. Jest tutaj tylko taki mały szkopuł, że odliczanie powinno się zaczynać od liczby zero i od wskazania gracza g_0.

Następnie zauważmy, że wybór liczb przez graczy ograniczony liczbą palców (zwyczajowo od jednego do dziesięciu) w większości przypadków (w modelu klasycznego prawdopodobieństwa) powoduje, że szanse graczy na wybranie rozkładają się nierównomiernie.

Przykład 1.

Mamy trzech graczy i zakładamy model klasycznego prawdopodobieństwa. Przestrzeń zdarzeń elementarnych to wszystkie możliwe wybory trójki graczy spośród ilości palców od jednego do dziesięciu:

\Omega=\{(x_0,x_1,x_2): x_i \in \{1, 2, \dots 10\} \}.

Prawdopodobieństwo dowolnego A \subset \Omega zdefiniowane jest wzorem

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

Oczywiście \# \Omega = 10^3.

Oznaczmy teraz dla r=0,1,2 zbiory

W_r=\{(x_0,x_1,x_2) \in \Omega: x_0+x_1+x_2 \equiv r \mod 3 \}

zdarzeń sprzyjających wyborowi k-tego gracza.

Chcielibyśmy, aby

\displaystyle \frac{1}{3}=\frac{\# W_r}{10^3}

czyli aby

\#W_r=\frac{10^3}{3}

ale prawa strona nie jest liczbą naturalną.

Widać zatem, że nie może być mowy o równych szansach i to z przyczyn czysto technicznych. Nie możemy zatem ograniczać się wyłącznie do liczby palców. Będziemy zakładać chwilowo, że gracze wybierają spośród skończonego podzbioru liczb naturalnych Z, który będziemy nazywać zakresem. Ogólnie możemy sformułować następujący warunek.

Warunek konieczny.

Dla dowolnej liczby graczy n (i dowolnego zakresu Z), jeśli gracza mają równe szanse, to

n|\# \Omega.

Jest to oczywisty i powiedziałbym, że techniczny warunek. W tym sensie, że w ogóle nie zależy od tego jak zbiory W_r są zdefiniowane. Zależy jedynie od liczności zakresu i liczby graczy, które determinują liczność \Omega.

Oczywiście tak słaby warunek nie może być wystarczający. Rozważmy następującą sytuację.

Przykład 2.

Załóżmy, że mamy czterech graczy wybierających spośród zakresu liczb Z=\{0,1\}. Wtedy \# \Omega=16 i dzieli się przez liczbę graczy, jednak graczowi zerowemu sprzyjają jedynie wybory (0,0,0,0) , (1,1,1,1). Widać więc, że jego szanse to \frac{2}{16} i są one mniejsze od \frac{1}{4}.

Warunek konieczny przydaje się więc głównie, aby łatwo przekonać niedowiarków, że nie zawsze mogą być równe szanse. Można też oczywiście dobrać do każdej liczby graczy taki zakres, by nie było równych szans. Dla n graczy przykładowo będzie to zbiór \{0, 1, \dots n-1\} z wyrzuceniem jednego z elementów.

Warunek wystarczający.

W modelu klasycznego prawdopodobieństwa warunkiem wystarczającym na równe szanse wszystkich graczy jest aby, gdy w grze uczestniczy n graczy, zakresem liczb, spośród których wybierają gracze, był zbiór Z=\{0,1,\dots n-1\}.

Można tego faktu dowieść na przynajmniej trzy sposoby korzystające jedynie z własności teorioliczbowych i arytmetycznych. Zaprezentuję ten, wykorzystujący systemy pozycyjne.

Dowód.

Mamy przestrzeń zdarzeń elementarnych

\Omega=\{(x_0,x_1,\dots x_{n-1}): x_i \in\{0,1,\dots n-1\} \}

Mamy też zbiory

W_r=\{(x_0,x_1,\dots x_{n-1}) \in \Omega: x_0+x_1+ \dots + x_{n-1} \equiv r \mod n \}

dla r=0,1, \dots n-1

Ponieważ \# \Omega =n^n, naszym celem jest wykazanie, że \# W_r=n^{n-1}.

Zauważmy, że zdarzenia elementarne możemy interpretować jak liczby całkowite w systemie o podstawie n. Będziemy je interpretować w naturalny sposób poprzez funkcję

T: \Omega \ni (c_{n-1}, \dots c_1, c_0) \mapsto c_{n-1}n^{n-1}+\dots + c_1n+c_0 \in \mathbb{N}.

Czyli bierzemy n-kę uporządkowaną jako liczbę c_{n-1}\dots c_1c_0 i przypisujemy jej wartość w systemie dziesiątkowym. Zauważmy, że obrazem dziedziny przez funkcję T będzie zbiór \{0, 1, \dots n^n-1 \}, gdyż

0\leq c_{n-1}n^{n-1}+\dots + c_1n+c_0 \leq (n-1) n^{n-1} + \dots + (n-1)n +n-1=n^n-1

Oczywiście przedstawienie liczb jest jednoznaczne, więc będziemy mieli bijekcję pomiędzy \Omega a zbiorem \{0, 1, \dots n^n-1 \}.

Będziemy badać przeciwobrazy n kolejnych liczb naturalnych z T(\Omega), to jest zbiory postaci A_k=\{kn, kn+, \dots kn+n-1\}, gdzie k przebiega wszystkie liczby naturalne od 0 do n^{n-1} - 1. Ważną własnością jest, że dwie kolejne liczby m,m+1\in A_k różnią się od siebie o jeden ostatnią cyfrą i żadną inną, gdy patrzymy na nie w systemie o podstawie n. W języku funkcji T zachodzi

T^{-1}(m)=(c_{n-1}, \dots c_1, c_0), a T^{-1}(m+1)=(c_{n-1}, \dots c_1, c_0+1).

Za chwilę wyjaśnimy dlaczego tak się dzieje. Przed tym omówimy ideę dowodu. Elementy \Omega, zinterpretowane jako liczby w systemie pozycyjnym o podstawie n porządkujemy wg wartości w systemie dziesiątkowym.

\begin{array}{lcl}  (0, \dots,0, 0) && 0 \\  (0, \dots,0, 1)&&1 \\  \hfil\vdots\hfil&&\vdots \\  (0, \dots, 0, n-1)&&n-1 \\  (0, \dots, 1, 0)&&n \\  (0, \dots, 1, 1)&&n+1 \\  \hfil\vdots\hfil&&\vdots \\    \end{array}

Gdy weźmiemy każde kolejne n liczb naturalnych (ze zbioru wartości), to odpowiada im dokładnie n liczb w systemie o podstawie n. Również możemy powiedzieć o nich, że są koleje, bo różnią się jedynie cyfrą na ostatniej pozycji, a dwie sąsiadujące liczby różnią się na ostatniej pozycji o jeden. Zatem sumy ich cyfr tworzą także ciąg n kolejnych liczb całkowitych. Te po wydzieleniu z resztą przez n tworzą ciąg wszystkich możliwych reszt z dzielenia przez n. Zatem w każdym ciągu n kolejnych elementów \Omega znajdzie się dokładnie jedna n-ka uporządkowana sprzyjająca wylosowaniu każdego z graczy, a ponieważ możemy zbiór wartości wydzielić na równą ilość takich ciągów n-elementowych dostaniemy, że graczom przypada po równo sprzyjających n-ek. Za chwilę to jeszcze raz zapiszemy, ale formalnie.

Wracając do dowodu oznaczmy

T^{-1}(m)=(c_{n-1}, \dots c_1, c_0), a T^{-1}(m+1)=(c'_{n-1}, \dots c'_1, c'_0).

Po pierwsze z algorytmu Hornera wiemy, że zerową cyfrą danej liczby jest zawsze jej reszta z dzielenia przez podstawę systemu. Możemy więc zapisać

T^{-1}(m)=(c_{n-1}, \dots c_1, r_n(m)), a T^{-1}(m+1)=(c'_{n-1}, \dots c'_1, r_n(m+1)

Z jednoznaczności dzielenia z resztą i postaci liczb m, m+1 mamy

m=kn+r_n(m) oraz  m+1=kn+r_n(m+1).

Zatem odejmując stronami

1=r_n(m+1)-r_n(m)

Równoważnie

r_n(m+1)=r_n(m)+1=c'_0=c_0+1

A więc wykazaliśmy, że rzeczywiście ostatnie cyfry m oraz m+1 różnią się o jeden.

Jednocześnie ponieważ

m+1=(c_{n-1}n^{n-1}+\dots + c_1n+c_0) +1=c_{n-1}n^{n-1}+\dots + c_1n+(c_0 +1)

więc c_{n-1}\dots c_1 (c_0+1) też jest przedstawieniem liczby m+1, ale jak wiemy, jest ono jedyne, zatem

T^{-1}(m+1)=(c_{n-1}, \dots c_1, c_0+1).

Wniosek stąd taki, że gdy oznaczymy przez T^{-1}(nk)=(c_{n-1}, \dots c_1, 0), to otrzymamy, że

T^{-1}(nk)=(c_{n-1}, \dots c_1, 0)

T^{-1}(nk+1)=(c_{n-1}, \dots c_1, 1)

\vdots

T^{-1}(nk+n-1)=(c_{n-1}, \dots c_1, n-1)

Zatem możemy zapisać, że

T^{-1}(A_k)= \{(c_{n-1}, \dots c_1, 0), (c_{n-1}, \dots c_1, 1), \dots (c_{n-1}, \dots c_1, n-1)\}

Idąc dalej, zbadajmy sumy cyfr liczb z powyższego zbioru. Oznaczmy przez

l=c_{n-1}+\dots+c_2+c_1

sumę wspólnych cyfr.

Wtedy sumy cyfr wszystkich liczb ułożą się w ciąg l, l+1, \dots l+n-1. Jest to ciąg n kolejnych liczb całkowitych, a o nim wiemy, że

\{r_n(l), r_n(l+1), \dots r_n(l+n-1)\}=\{0,1, \dots n-1\}

Mamy więc, że dla dowolnego r \in \{0, 1, \dots n-1\} oraz k\in \{0, 1, \dots n^{n-1}-1\} przecięcie

W_r \cap T^{-1}(\{kn, kn+1, \dots kn+n-1 \})=

\{ (c_{n-1}, \dots c_1, c_0) \in \Omega: c_{n-1}+ \dots + c_1+ c_0 \equiv r \mod n,T(c_{n-1}, \dots c_1, c_0) \in A_k \}

zawiera dokładnie jeden element.

Uwzględniając, że zbiory A_k są parami rozłączne oraz

\displaystyle \bigcup_{k=0}^{n^{n-1}-1} A_k=\bigcup_{k=0}^{n^{n-1}-1} \{ kn, kn+1, \dots kn+n-1 \}= \{0 ,1, \dots n^n-1 \} = T( \Omega)

dostajemy

\displaystyle \# W_r= \# \left( \bigcup_{k=0}^{n^{n-1}-1}W_r \cap T^{-1}(A_k) \right)= \sum_{k=0}^{n^{n-1}-1} \# \left( W_r \cap T^{-1}(A_k) \right)=\sum_{k=0}^{n^{n-1}-1} 1

A więc, że \# W_r=n^{n-1}, co należało pokazać.

Jednak powyższy dowód należy głównie traktować jako ciekawostkę. Metodami bardziej elementarnymi można wykazać mocniejszy rezultat, wystarczy jedynie zastosować bardziej ogólny model – traktować graczy jak zmienne losowe.

Będziemy więc utożsamiać graczy z ich wyborami czyli ze zmiennymi losowymi o wartościach całkowitych.

Sumą liczb wybranych przez graczy g_0, g_1, \dots g_{n-1} będzie kolejna zmienna losowa

\displaystyle S=\sum_{k=0}^{n-1} g_k

Natomiast numerek wygranego gracza, gdy losujemy spośród n graczy będzie zmienną losową określoną wzorem

O=r_n(S)

Jednak będziemy zajmować się bardziej ogólną sytuacją, tzn. badać zmienne losowe określone jako

\displaystyle r_m\left( \sum_{k=1}^n \xi_k \right),

gdzie \xi_k to zmienne losowe o wartościach całkowitych, m>1 jest liczbą naturalną. Celowo rozmija się tutaj n z m, ilość zmiennych losowych nie będzie miała w pewnych warunkach żadnego znaczenia. Przy takim określeniu będzie nas interesowało kiedy zachodzi

\displaystyle P \left( r_m\left( \sum_{k=1}^n \xi_k \right) = r \right) =\frac{1}{m}

dla dowolnej reszty r=0, 1, \dots m-1. Zauważmy, że gdy n=m to mamy sytuację z gry w marynarza. Przedstawię teraz najistotniejsze twierdzenie z mojej pracy wraz z poglądową wersją dowodu.

Twierdzenie.

Ustalmy dowolną liczbę naturalną m>1. Dane niech będą zmienne losowe \xi_1, \xi_2, \dots \xi_n przyjmujące wartości ze zbioru \{0, 1, \dots m-1 \}. Załóżmy, że dla pewnego i_0 \in \{1, 2, \dots n\} zachodzą warunki

  1. Każdą resztę r \in \{0, 1, \dots m-1 \} zmienna losowa \xi_{i_0} przyjmuje z prawdopodobieństwem \frac{1}{m}.
  2. Zmienne losowe \xi_{i_0} oraz \displaystyle r_m \left(\sum_{i=0,i\neq i_0}^n \xi_i \right) są niezależne.

Wtedy zmienna losowa \displaystyle r_m \left(\sum_{i=0}^n \xi_i \right) także przyjmuje każdą resztę z prawdopodobieństwem \frac{1}{m}.

Interpretacja na grę w marynarza jest następująca. Losujemy spośród m osób, ale liczby do losowania podaje n graczy. Mamy przynajmniej jednego sprawiedliwego gracza \xi_{i_0}, który wybiera swoje liczby niezależnie od tego na kogo wskażą pozostali wspólnie (warunek 2) i wybiera każdą osobę z takim samym prawdopodobieństwem (warunek 1). W pracy dosyć szczegółowo omawiam, że istotnie można tak patrzyć na założenia. Dodatkowo założenie niezależności z warunku drugiego jest słabszym warunkiem od niezależności wszystkich graczy. Tak więc gra jest sprawiedliwa jeśli tylko jeden gracz jest sprawiedliwy. Pozostali mogą mieć najróżniejsze preferencje (rozkłady) w doborze liczb, a także mogą nawet być w zmowie (mogą być zależni).

Dowód.

Zauważmy, że

\displaystyle r_m \left(\sum_{i=0}^n \xi_i \right) =r_m \left(\xi_{i_0} +\sum_{i=0,i\neq i_0}^n \xi_i \right)= r_m \left(\xi_{i_0} +r_m\left(\sum_{i=0,i\neq i_0}^n \xi_i\right) \right)

Oznaczając X:=\xi_{i_0} oraz \displaystyle Y:= r_m \left( \sum_{i=0, i\neq i_0}^n \xi_i \right) widzimy, że nasz problem sprowadza się do wykazania, że

P(r_m(X+Y)=r)=\frac{1}{m}

dla dowolnej reszty r \in \{0,1, \dots m-1 \}, a więc do sytuacji dwóch graczy (to jest powód, dla którego ilość zmiennych losowych n nie gra większej roli).

Ustalmy zatem resztę r \in \{0,1, \dots m-1 \} i zdefiniujmy zbiór

O_r=\{(x,y): x,y\in \{0,1, \dots m-1\}, r_m(x+y)=r \}

tych wszystkich możliwych wyborów dwóch graczy, dla których wybrany zostaje gracz r-ty.

Wykonujemy teraz przekształcenia

\displaystyle P(r_m(X+Y)=r)=P \left( \bigcup_{(x,y) \in O_k} \{X=x,Y=y\} \right)

A dalej z własności miary otrzymujemy, że powyższe prawdopodobieństwo jest równe

\displaystyle \sum_{(x,y)\in O_k}P(X=x,Y=y)

Teraz z założenia o niezależności mamy, że powyższa suma równa jest

\displaystyle \sum_{(x,y)\in O_k}P(X=x)P(Y=y)

a ponieważ każdy x jest resztą z dzielenia przez m, więc z założenia o rozkładzie X

\displaystyle \sum_{(x,y)\in O_k}\frac{1}{m}P(Y=y)=\frac{1}{m}\sum_{(x,y)\in O_k}P(Y=y)

Pozostało jedynie do wykazania, że suma

\displaystyle \sum_{(x,y)\in O_k}P(Y=y)

wynosi jeden.

Ale można wykazać, że O_r=\{ (r_m(r-0), 0), (r_m(r-1), 1), \dots (r_m(r-[m-1]), m-1) \}.

Zatem

\displaystyle \sum_{(x,y)\in O_k}P(Y=y)=\sum_{y=0}^{m-1}P(Y=y)=1

gdyż zmienna losowa Y był zdefiniowana jako pewna reszta z dzielenia przez m, co kończy dowód.

Zachodzi też bardziej ogólne twierdzenie

Wniosek (uogólniony warunek wystarczający)

Ustalmy dowolną liczbę naturalną m>1. Dane niech będą zmienne losowe \xi_1, \xi_2, \dots \xi_n o wartościach całkowitych. Załóżmy, że dla pewnego i_0 \in \{1, 2, \dots n\} zachodzą warunki

  1. Każdą resztę r \in \{0, 1, \dots m-1 \} zmienna losowa r_m(\xi_{i_0}) przyjmuje z prawdopodobieństwem \frac{1}{m}.
  2. Zmienne losowe \xi_{i_0} oraz \displaystyle r_m \left(\sum_{i=0,i\neq i_0}^n \xi_i \right) są niezależne.

Wtedy zmienna losowa \displaystyle r_m \left(\sum_{i=0}^n \xi_i \right) także przyjmuje każdą resztę z prawdopodobieństwem \frac{1}{m}.

Tym razem bierzemy dowolne całkowite zmienne losowe, a rolę sprawiedliwego gracza przejmuje reszta z dzielenia jednego z graczy. Wniosek ten z grubsza zachodzi, dzięki temu, że

\displaystyle r_m\left( \sum_{i=1}^n \xi_i \right)=r_m\left( \sum_{i=1}^n r_m(\xi_i) \right).

Uogólniony warunek wystarczający pozwala np. podmienić zakres \{0,1 \dots m-1\} na \{1, 2, \dots m\}, a także na wiele innych równoważnych. Możemy też znaleźć różne wymyślne rozkłady czy zmienne losowe, dla których gra będzie sprawiedliwa.

Podam teraz mój ulubiony przykład z pracy prezentujący inne niż gra w marynarza zastosowanie powyższych rezultatów.

Przykład 3.

Spotyka się przy stole pewna liczba graczy. Jeden z nich jest uczciwy, a pozostali są szulerami. Każdy gracz posiada własną kostkę do gry. Kostki szulerów są tak zbudowane, że częściej wypadają korzystne dla nich liczby (np. szóstki), natomiast kostka uczciwego gracza jest symetryczna (każda liczba wypada z takim samym prawdopodobieństwem). Każdy z graczy chce grać własną kostką. Co zatem powinien zaproponować uczciwy gracz, aby rozgrywka była sprawiedliwa? Odpowiedź: Niech K_1, K_2, \dots K_n będą zmiennymi losowymi odpowiadającymi kostkom kolejnych graczy (siłą rzeczy zakładamy ich niezależność). Za każdym razem kiedy dany gracz będzie chciał rzucić swoją kością, będą rzucać wszyscy gracze, następnie oczka z wszystkich kostek zostaną zsumowane S := K_1 + K_2 + \dots + K_n a za wynik rzutu kością tego gracza uznana zostanie wartość zmiennej losowej r_6 (S ) + 1. Zauważmy, że kostki spełniają założenia Uogólnionego warunku wystarczającego dla dla m = 6 ponieważ ich zakres to \{1, 2, 3, 4, 5, 6 \}. Kostka uczciwego  gracza przyjmuje każdą wartość z równym prawdopodobieństwem, a dodatkowo z niezależności kostek wynika odpowiednia niezależność kostki gracza uczciwego od reszty z dzielenia sumy kostek szulerów. Zatem zmienna losowa r_6(S) przyjmuje każdą z liczb 0, 1, 2, 3, 4, 5 z prawdopodobieństwem \frac{1}{6}. Dodanie jedynki służy tylko sprowadzeniu wyników do wartości oczek na kostce. Mamy więc demokratyczne wyjście, gdzie każdy z graczy rzuca własną kością, a przy którym nie jest możliwe oszukiwanie.

Hipoteza.

Jest jeszcze jeden nierozwiązany problem. Przy założeniu, że wszyscy gracze wybierają niezależnie, ze wspólnego zakresu i każdą liczbę z równym prawdopodobieństwem mamy w rzeczywistości model z klasycznym prawdopodobieństwem. Uważam, że wtedy Uogólniony warunek wystarczający będzie także warunkiem koniecznym. Tzn. jedyna postać zakresu jaka będzie dawała równe szanse to uogólniona postać zakresu (wynika z Uww a można ją też znaleźć w prezentacji, którą także udostępnię). Być może zakres ten mógłby być przy słabszych założeniach dotyczących niezależności.

Pliki.

Pod poniższymi adresami można znaleźć moją pracę, a także prezentację w Power Poincie, która zawiera moje wczesne badania nad grą w marynarza (w sytuacji klasycznego prawdopodobieństwa – kolejny alternatywny dowód), które zaprezentowałem na Wigilii Bożego Narodzenia zorganizowanej przez koło naukowe matematyków PWSZ w Tarnowie.  Google Disc posiada wbudowaną przeglądarkę plików, ale w przypadku prezentacji  nie radzi ze wszystkimi symbolami, więc sugeruję ją po prostu ściągnąć, jeśli ktoś chce czytać.

Google Disc: link 1

Praca na przeklej.net: link 2

Advertisements

Jedna uwaga do wpisu “Gra w marynarza

  1. Pingback: Gra w marynarza – dalsze własności | Różne matematyka

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s