Problem Józefa Flawiusza

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
SoD
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 3 lis 2004, o 18:34
Płeć: Mężczyzna
Lokalizacja: L-ca

Problem Józefa Flawiusza

Post autor: SoD » 26 gru 2004, o 21:52

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

Awatar użytkownika
g
Użytkownik
Użytkownik
Posty: 1554
Rejestracja: 21 sie 2004, o 16:44
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 59 razy

Problem Józefa Flawiusza

Post autor: g » 27 gru 2004, o 12:36

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

Yavien
Gość Specjalny
Gość Specjalny
Posty: 800
Rejestracja: 21 cze 2004, o 22:20
Płeć: Kobieta
Lokalizacja: W-U

Problem Józefa Flawiusza

Post autor: Yavien » 27 gru 2004, o 15:32

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

SoD
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 3 lis 2004, o 18:34
Płeć: Mężczyzna
Lokalizacja: L-ca

Problem Józefa Flawiusza

Post autor: SoD » 27 gru 2004, o 23:10

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
Gość Specjalny
Gość Specjalny
Posty: 800
Rejestracja: 21 cze 2004, o 22:20
Płeć: Kobieta
Lokalizacja: W-U

Problem Józefa Flawiusza

Post autor: Yavien » 27 gru 2004, o 23:35

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
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 3 lis 2004, o 18:34
Płeć: Mężczyzna
Lokalizacja: L-ca

Problem Józefa Flawiusza

Post autor: SoD » 28 gru 2004, o 17:36

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

Awatar użytkownika
mgol
Użytkownik
Użytkownik
Posty: 96
Rejestracja: 13 sty 2005, o 15:52
Płeć: Mężczyzna
Lokalizacja: Warszawa / Stalowa Wola

Problem Józefa Flawiusza

Post autor: mgol » 14 sty 2005, o 11:46

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

arcan
Użytkownik
Użytkownik
Posty: 106
Rejestracja: 17 gru 2012, o 23:56
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 7 razy
Pomógł: 31 razy

Problem Józefa Flawiusza

Post autor: arcan » 21 maja 2013, o 11:51

SoD pisze:(..)
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
Użytkownik
Użytkownik
Posty: 7249
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 3 razy
Pomógł: 939 razy

Re: Problem Józefa Flawiusza

Post autor: Kartezjusz » 4 maja 2019, o 23:52

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

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6695
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1216 razy

Re: Problem Józefa Flawiusza

Post autor: mariuszm » 15 maja 2019, o 22:38

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

ODPOWIEDZ