Problem Józefa Flawiusza

[SoD]

Chyba wiekszosc osob na forum wie jak wyglada problem Józefa flawiusza, ale pokrótce go opiszę:

Dawno temu, podczas wojny rzymsko-żydowskiej Flawiusz wraz z grupą 41 żydowskich powstańców został otoczony przez Rzymian w jaskini! Woląc samobójstwo od poddania powstancy postanowili utworzyć krąg i zabijać co trzecią osobę, aż nikt nie pozostanie przy zyciu! Jednak Flawiusz wraz z przyjacielem nie zgadzali się na to bezsensowne samobójstwo i szybko wyliczył, gdzie powinni stanąć on i jego przyjaciel aby jako ostatni zostali tylko oni!

Ten problem jest rozwiązany, dla n osob i jezeli zabija się co drugą osobę i chcemy aby jedna została, w ksiażce: "Matematyka konkretna" Graham, Knuth i Patashnik.

A czy moze ktos umie rozwiazać, lub zna rozwązanie do pierwotnej treści zadania czyli gdy zabijana jest co trzecia osoba i trzeba obliczyc dwa ostatnie uratowane miejsca?
Konkretnie to trzeba znaleźć wzór pozwalający wyznaczyć J_1(n) i J_2(n) znając wartości J_1(m) oraz J_2(m) dla m

[g]

16 i 31 - to jest wynik jesli cie ciekawi, w ksiazce S. Kowala "Przez rozrywke do wiedzy" jest podany wraz z recznym rozwiazaniem

[Yavien]

a mi recznie wyszlo 17 i 32, pewnie zalezy od poczatku

[SoD]

No poprawny wynik to 16 i 31 tyle to ja umiem wyliczyc recznie co nie jest trudne, a na dodatek napisalem program ktory to wylicza i to dla n osob i co m zabijanego! Tylko ze problem polega na tym aby znalezc wzor rekurencyjny na to, czyli jak sie zabija co 3 osobe to ktore dwie zostana w zaleznosci od liczby osob. Dla zabijanej co drugiej osoby to taki wzor wyglada:
\(\displaystyle{ J(1)=1}\)
\(\displaystyle{ J(2n)=2J(n)-1}\) dla n >=1
\(\displaystyle{ J(2n+1)=2J(n)+1}\) dla n >=1

Kożystajac z tych wzorow mozna obliczyc dla kazdego n.

Dalej w Matematyce Konkretnej wyprowadzaja na to wzór:
\(\displaystyle{ J(2^m + L) = 2L +1}\)

Moze sprobuje to ladniej napisac:

\(\displaystyle{ J(2^m+l)=2l+1}\)

No i jeszcze co ciekawe to ostatnie uratowane miejsce to jak zapisze sie liczbe osob w systemie binarnym i przesunie o jeden bit zdaje sie w lewo to bedzie numer tego uratowanego miejsca! jezeli ktos nie wie co to znaczy przesunac o bit to to jest to samo co wziac pierwsza cyfre i dac ja na koniec!

No i ja poszukuje czegos podobnego dla tej wersji gdzie zabija sie co trzecia osobe!
A przynajmniej cos takiego jak te trzy pierwsze wzory!

[Yavien]

Poprawka do mojego poprzedniego: wyszlo mi recznie 19 i 34, ale ja liczylam, ze osob nie jest 41, bo przeciez

Flawiusz wraz z grupą 41 żydowskich powstańców

Dla mnie to znaczy, ze osob bylo 42.

J(m) to jest co? numer (wyjsciowy) osoby, ktora zostanie zabita w m tym ruchu? czy numer osoby, ktora zostanie na koncu, jesli poczatkowo osob bylo m?

[SoD]

A no masz racje mozna brac pod uwage ze lacznie bylo ich 42 osoby i wtedy poprawne wyniki to:
\(\displaystyle{ J_1(42)=19}\) i \(\displaystyle{ J_2(42)=34}\)


Jest tak:
dla przypadku gdzie zabija sie co druga osobe to:
J(n) jest to ostatnia zywa osoba kiedy zabija sie co druga osobe sposrod n liczby osob!

a dla przypadku gdy zabija sie co trzecia osoba to :
\(\displaystyle{ J_1(n)}\) to jest pierwsza z dwoch pozostalych osob kiedy zabijaja co trzecia osobe z grupy n osob

natomiast \(\displaystyle{ J_2(n)}\) to jest druga z pozostalych osob

[mgol]

Ale w "Matematyce Konkretnej" problem ogólny też jest rozwiązany, tylko przy końcu rozdziału...

[arcan]

(..)
Dalej w Matematyce Konkretnej wyprowadzaja na to wzór:
\(\displaystyle{ J(2^m + L) = 2L +1}\)

Moze sprobuje to ladniej napisac:

\(\displaystyle{ J(2^m+l)=2l+1}\)
(...)

Witam, bardzo ciekawy wzór rekurencyjny podałeś dla przesunięcia o dwa. nie spodziewałem się że to można w tak łatwy sposób napisać. Jednak nie rozumiem tej części:
\(\displaystyle{ J(2^m + L) = 2L +1}\)
\(\displaystyle{ J(2^m+l)=2l+1}\)
Czyli dla pomijanie co dwa rozumiem, ale co m już nie potrafię pojąć.
Czy mógłby mi ktoś to wytłumaczyć tak łopatologicznie?

[Kartezjusz]

A jak ( z dowodem ) przejść z wersji pierwotnej do takiej, że najpierw zabijamy nieparzystych. Zabijamy od 1

[Mariusz M]

Kartezjusz, wątpie aby tobie odpowiedzieli skoro od lat już nikt nie kontynuuje tego wątku

SoD, się tutaj chwalił że napisał program

Program jest łatwiejszy do napisania niż sito Eratostenesa dla liczb pierwszych

Program można napisać albo z użyciem tablicy
(do indeksowania przydaje się arytmetyka modularna)
albo z użyciem listy cyklicznej