Raz, dwa, trzy, wychodź ty!

Dawno temu... w czasach bez Internetu, bez gier komputerowych i smartfonów dzieci bawiły się w chowanego. Na początku zabawy trzeba było oczywiście wyznaczyć osobę, która będzie szukać. Uczestnicy ustawiali się w koło i ktoś odliczał: Raz, dwa, trzy, wychodź ty, i wówczas szósta osoba (odliczanka ma 6 sylab) wychodziła z kółka. Procedurę tę powtarzano aż do momentu, gdy w kółku pozostała jedna osoba - to był pierwszy szukający. Istnieje wiele wierszyków-odliczanek. Moją ulubioną jest odliczanka 15-sylabowa: Mama daje jeść, tata daje pić, a ty sobie idź.

Bardzo dawno temu... dokładniej prawie 2 tysiące lat temu, Flawiusz wraz z grupą powstańców został otoczony w jaskini. Powstańcy zdecydowali, że nie poddadzą się i nie dadzą się pojmać żywcem. Postanowili więc losować: "w jakiej kolejności mamy jeden drugiego zabijać. Pierwszy, na którego padnie, niech zginie z ręki następującego po nim" (cytat z dzieła Flawiusza). W opisie nie było szczegółów na temat losowania i wątpię, czy historyk myślał o jakimkolwiek matematycznym aspekcie tego zagadnienia. Jako pierwszy matematyczną postać temu zdarzeniu nadał francuski matematyk Claude Gaspar Bachet de Méziriac (1581-1638). Według niego powstańcy po ustawieniu się w okrąg mieli eliminować co trzeciego spośród siebie. Nie wiadomo, ilu było powstańców, niektóre źródła podają, że czterdziestu (wraz z Flawiuszem), inne, że czterdziestu jeden. Można też spotkać wersję z co siódmym eliminowanym uczestnikiem "śmiertelnej odliczanki".

Załóżmy, że liczby od $1$ do $n$ ustawiono na okręgu (patrz Rys. 1). Posuwając się zgodnie z ruchem wskazówek zegara, skreślamy co $k$ -tą liczbę. Oczywiście w kolejnym okrążeniu nie uwzględniamy w odliczance skreślonych wcześniej liczb. Zajmiemy się problemem szukania ostatniej nieskreślonej liczby spośród $n,$ gdy wykreślamy co $|k$ -tą. Oznaczmy ją przez $J(n,k)$ i nazwijmy liczbą szczęśliwą. Zagadnienie to nosi nazwę problemu Flawiusza (Josephus Problem). Spójrzmy na kolejne skreślenia dla $|n = 7$ oraz $k = 3$ :

Wynika stąd, że $|J(7,3) = 4.$

Jak obliczać $J n, k ?$ Oczywiście wartości można wyznaczać "ręcznie", ale dla większych $n$ jest to niewygodne. Napiszmy program do obliczania liczb szczęśliwych. Poniżej prezentujemy procedurę napisaną w programie MATHEMATICA (ilustrujemy ją przykładem dla $n = 7$ oraz $|k = 3$ ).

Wartości $|J n,2 .$ Spójrzmy na tabelkę, w której zamieszczono liczby szczęśliwe dla $n$ w zakresie od 1 do 20, gdy skreślamy co drugą liczbę:

$|-------|--|--|--|--|--|--|--|--|--|---|---|---|--|---|---|---|---|---|--|----| ---n-----1--2--3--4--5--6--7--8--9---10--11--12--13--14--15--16--17--18--19---20-| | | | | | | | | | | | | | | | | | | | | | | -J(n,2)--1--1--3--1--3--5--7---1-3---5---7--9---11--13--15---1--3---5---7---9--|$

Prawidłowość jest ewidentna. Można nawet pokusić się o odgadnięcie wzoru jawnego:

J(n,2) = 2(n − 2 log2n )+ 1.

(*)

W dowodzie wzoru $(∗)$ korzysta się z dwóch zależności rekurencyjnych:

J(2n, 2) = 2J(n,2) − 1, J(2n +1,2) = 2J(n, 2)+ 1.

Okazuje się, że jawny wzór na $J(n, k)$ jest znany jedynie dla $k = 2.$

$|J n,k$ dla $k > 2$ - problem otwarty. Spójrzmy na poniższą tabelkę:

$|------|-|--|--|--|-|--|--|-|--|---|--|--|--|---|--|--|---|--|--|---| |--n---|1|2-|3-|4-|5|6-|7-|8|9-|10-11-|12-|13|14-|15-|16-|17-|18-|19-|20-| |J n,3 |1|2 |2 |1 4 |1 |4 |7| 1|4 |7 |10 |13| 2 |5 |8 |11 |14 |17|20 | ---------------------------------------------------------------------$

Wartości $|J(n, 3)$ są przedstawione obok dla $|n = 1,2,...,100.$ Można dostrzec następującą prawidłowość: od $n = 4$ występują "bloki" coraz dłuższych ciągów arytmetycznych o przyroście 3.

Pójdźmy jeszcze tropem wyznaczonym przez Andrew M. Odlyzko oraz Herberta S. Wilfa, którzy w pracy [1] z 1991 roku zaproponowali następujący wzór:

⎢ 2n--1⎥ ⎢⎢ 3- log32 K ⎥⎥ J(n, 3) = 3n + 1− ⎢⎢K(3) , (2) ⎥⎥ ⎣ ⎦

gdzie $K(3)$ jest stałą (obliczoną za pomocą dość skomplikowanej procedury), której wartość do 9-go miejsca po przecinku wynosi 1,622705028. Jawny wzór, nieodwołujący się do żadnych innych procedur, dla $J(n, | k),$ gdy $|k > 2$ nie jest znany.

Inny trop, permutacje - i zaskakująca puenta. Pewne zastosowanie problemu Flawiusza można znaleźć w książce Israela N. Hersteina i Irvinga Kaplansky'ego Matters Mathematical [2]. Autorzy używają tak zwanych permutacji Josephusa. Wyjaśnimy to na przykładzie $|J(8,2)$ : w ręcznym wykreślaniu eliminowane są kolejno 2, 4, 6, 8, 3, 7, 5. Na końcu ciągu dopiszmy nieskreślone 1. Kolejność skreślania można zapisać w postaci permutacji

P(8,2) = (1 2 3 4 5 6 7 8) . 2 4 6 8 3 7 5 1

Każdą permutację możemy przedstawić w postaci rozłącznych cykli, w naszym przypadku: $P (8,2) = (1248)(3675).$ Analogicznie można postąpić dla dowolnego $n.$ Herstein i Kaplansky odkryli, że jeśli $|n$ oraz $|2n +1$ są liczbami pierwszymi oraz $n$ jest postaci $|4k +3,$ to permutacja $|P(n,2)$ jest iloczynem dwóch rozłącznych cykli. Długości tych cykli dla wybranych $|n$ umieszczono w tabelce poniżej.

Zanim opiszemy kolejne odkrycie Hersteina i Kaplansky'ego, przedstawimy kilka informacji dotyczących ciał liczbowych. Czytelnicy doskonale znają liczby wymierne oraz ich bogatą strukturę algebraiczną - z dodawaniem i odejmowaniem, mnożeniem i dzieleniem zbiór $Q$ tworzy ciało. A co się stanie, gdy rozszerzymy zbiór $Q$ o jakiś element niebędący liczbą wymierną? Powinniśmy przy tym zadbać, aby algebraicznie nowy zbiór nic nie "stracił", to znaczy pozostał ciałem. Przykład takiego rozszerzenia podał Gauss, jest to ciało Gaussa: $Q(i) = {a + ib a,b ∈ Q}.$ Z kolei o pierścieniu Gaussa $|Z(i) = {a + ib a, b∈ Z}$ można powiedzieć, że jest tym dla ciała $|Q(i),$ czym dla $Q$ są liczby całkowite $Z.$ Kluczowa własność zbioru liczb całkowitych to rozkładalność na czynniki pierwsze i jednoznaczność tego rozkładu. Okazuje się, że w pierścieniu Gaussa liczby także są jednoznacznie rozkładalne na czynniki pierwsze.

$|---|----------------------------------| | | | |-n-|-dł ugo-śćrozłącznych-cykli w-P(n,2)-| | 3 | 2,1 | |---|----------------------------------| |11 | 7,4 | |---|----------------------------------| |23 | 14,9 | |---|----------------------------------| |83-|---------------47,36---------------| | | | -131----------------72,59----------------$

Pojęciem ogólniejszym od ciała Gaussa są ciała liczbowe postaci $Q( θ),$ gdzie $|θ$ jest liczbą algebraiczną (czyli pierwiastkiem wielomianu o współczynnikach całkowitych). Ciało Gaussa jest ciałem liczbowym, $| √ --- i = −1$ jest pierwiastkiem wielomianu $2 x + 1.$ Dla ciał liczbowych rozpatruje się pierścienie "liczb całkowitych" tych ciał i bada własność jednoznaczności rozkładu tych pierścieni. Ta własność ma fundamentalne znaczenie przy rozwiązywaniu równań diofantycznych, na przykład równania Fermata $| n n n x + y = z .$ Batalia o dowód, że równanie Fermata nie ma rozwiązań w dodatnich liczbach całkowitych dla każdego $|n⩾ 3,$ zakończyła się dla wielu wybitnych matematyków klęską. Przyjmowali oni bowiem błędne założenie, że pewne pierścienie mają własność jednoznaczności rozkładu.

Jeśli $θ$ jest pierwiastkiem wielomianu kwadratowego o współczynnikach całkowitych, to możemy zakładać, że $| √ -- θ = d,$ gdzie $| d$ jest bezkwadratową liczbą całkowitą. Wówczas pierścień liczb całkowitych ciała $√ -- Q ( d )$ to po prostu $√ -- Z ( d) ,$ wtedy gdy $|d$ jest postaci $4k + 2$ lub $4k + 3.$ Natomiast dla liczb postaci $4k + 1$ ten pierścień to $1 -1√ -- Z (2 + 2 d) .$

Przykładem pierścienia, w którym nie ma jednoznaczności rozkładu, jest $√ --- Z ( − 5).$ W pierścieniu tym mamy na przykład $√ --- √ --- |6 = 2 ⋅3 = (1+ −5 )(1− −5 ).$ Aby badać problem jednoznaczności rozkładu w pierścieniach typu $Z (√ d-)$ lub $|Z (1+ 1√ d-), 2 2$ wprowadzono pojęcie liczby klas. Liczba klas ciała służy do rozpoznawania, czy wspomniane pierścienie mają własność jednoznaczności rozkładu, co zachodzi wtedy i tylko wtedy, gdy liczba klas jest równa 1. Udowodniono, że istnieje dokładnie dziewięć pierścieni ciał liczbowych $| √ -- Q ( d ),$ gdzie $|d$ jest bezkwadratową ujemną liczbą całkowitą, mających własność jednoznaczności rozkładu. Te liczby to: -1, -2, -3, -7, -11, -19, -43, -67, -163.

Powróćmy teraz do permutacji Josephusa. Przypomnijmy, że rozważamy takie $|n,$ że $|n$ oraz $|2n +1$ są liczbami pierwszymi oraz $|n$ jest postaci $| 4k+ 3.$ Okazało się, że długości cykli można wykorzystać do obliczania liczby klas niektórych ciał liczbowych postaci $√ --------- Q( − (2n+ 1)).$ W każdym takim ciele pierścień liczb całkowitych to $√ --------- |Z( 1+ 1 − (2n +1)). 2 2$ I tutaj niespodzianka: liczbę klas ciała $√ --------- Q( − (2n+ 1))$ można wyznaczyć, korzystając z długości cykli zamieszczonych w tabeli 1. Liczba klas ciała $√--- Q ( − 7)$ (czyli $|n = 3$ ) wynosi $2 −1 = 1,$ liczba klas ciała $Q (√ −23-)(n = 11)$ wynosi $|7− 4 = 3.$ Dla ciała $√ ---- Q ( −47 )(n = 23)$ mamy liczbę klas $14 − 9 = 5$ i tak dalej.

Przedstawiliśmy zadanie, problem Flawiusza, które ma już ponad 400 lat (de Méziriac opublikował je w książce wydanej w 1612 roku), ale wciąż wzbudza spore zainteresowanie. Mnóstwo informacji na ten temat można znaleźć w Matematyce konkretnej [3]. Zachęcamy do zapoznania się z tą piękną książką, zawierającą mnóstwo interesujących faktów dotyczących rozpatrywanych tu zagadnień.