Powrót Józefa

28 marca 2011
Marek Penszko

Przed trzema laty napomknąłem w Łamiblogu o tzw. problemie Flawiusza. Odpowiadając wówczas na jeden z komentarzy, napisałem o zamiarze popełnienia dłuższego artykułu na ten temat. Artykuł ukazał się w marcowym numerze „Świata Nauki”. Wspominam o tym, kontynuując temat błędów autorskich z poprzedniego wpisu, bowiem w artykule tym popełniłem pewien szczególny błąd… świadomie. Ciekaw byłem, czy ktoś z czytelników go zauważy. I nie zawiodłem się.
Krótko przypomnę sprawę Flawiusza, przytaczając klasyczną historyjkę, choć nieco zmodyfikowaną przez włoskiego matematyka Girolamo Cardano w XVI wieku.

Rzymianie otoczyli ukrytą w jaskini grupę 41 żydowskich powstańców. Jednym z nich, dowódcą, był Flawiusz (chodzi o autentyczną postać Józefa Flawiusza i rzeczywiste wydarzenie – wojnę żydowską, która miała miejsce w Judei w latach 66-73; imię Józef jest o tyle istotne, że rzymskim dowódcą w tej wojnie był także Flawiusz, ale Tytus). Aby nie zginąć z ręki wroga, otoczeni postanowili popełnić samobójstwo. Flawiusz, uważając, że byłby to ciężki grzech, zaproponował, aby wszyscy utworzyli okrąg i rozpoczęli wyliczankę do trzech, zabijając każdego co trzeciego, zaś samobójstwo popełniłby tylko ostatni. Wiele wskazuje na to, że była to propozycja sprytna i obłudna, choć Flawiusz wspomina, że „tak zrządził los albo Opatrzność Boża”, że został jako ostatni na „placu samozagłady” i…  poddał się Rzymianom, którzy darowali mu życie.

Problem polega, w konkretnym przypadku, na o ustaleniu, które miejsce zajął Flawiusz, by przeżyć, a w ogólnym przypadku brzmi tak:

poruszając się w kierunku zgodnym z ruchem wskazówek zegara po okręgu utworzonym z n ponumerowanych elementów, usuwamy – zaczynając od pierwszego – co k-ty element dotąd, aż pozostanie jeden; należy ustalić numer p tego ostatniego ocalonego elementu.

Wzór ogólny, określający zależność p od n i k nie jest znany, choć oczywiście „na piechotę” albo korzystając z programu można uporać się z konkretną sytuacją, czyli sprawdzić, że np. dla n = 41 i k  = 3 Flawiusz miał numer p = 31. Nietrudno także poradzić sobie w pewnej szczególnej sytuacji: tuż przed rozpoczęciem wyliczanki do kółka dołącza jedna osoba, czyli n wzrasta do 42. Flawiusz, aby przeżyć, powinien wówczas przesunąć się o trzy miejsca w lewo (p = 34), ponieważ gdy n zwiększa się o 1, to p wzrasta o k. A to dlatego, że po pierwszym odliczeniu o k powstanie sytuacja taka, jak przy 41 osobach. Jeśli zatem znamy p dla n i k, to możemy łatwo policzyć, jakie będzie dla n+1 i k. „Wzorowo” wygląda to tak:

p (n+1, k) = [p (n, k) + k] (mod n+1)

albo jeszcze ogólniej, czyli gdyby do kółka dołączyło x osób:

p (n+x, k) = [p (n, k) + kx] (mod n+x)

I tu pojawia się „błąd”, który wyłapało kilku czytelników. Otóż ostatni wzór jest prawdziwy tylko dla x nie większych od pewnej wartości a, natomiast w artykule podałem przykład dla x większego o 1 od a.

Jaka jest wartość a:
1) w przypadku Flawiusza (n = 41, k = 3, p = 31)?
2) w ogólnym przypadku (wzór), czyli a = f (n, k, p)?

Kto czytał i pamięta wspomniany artykuł lub może do niego zajrzeć, dla tego udzielenie odpowiedzi na pierwsze pytanie jest trywialne, więc adresuję je do pozostałych. Będę natomiast niezmiernie zaskoczony, jeżeli pojawi się poprawna odpowiedź na drugie pytanie.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.