Baza wiedzy/Zagadki/Problem Józefa
Matematykatrudny

Problem Józefa

Problem Józefa
Problem Józefa Trzynaście osób w kole, co druga eliminowana; ocalałe miejsce to numer 11, zgodnie ze wzorem binarnym. Problem Józefa — kto ocaleje? 1 2 3 4 5 6 7 8 9 10 11 12 13 Eliminujemy co drugą osobę, idąc w koło (2, 4, 6…). Ocaleje miejsce 11. Wzór: dla n = 2ᵐ + l ocaleje 2l + 1. 13 = 2³ + 5 2·5 + 1 = 11 Sztuczka binarna: pierwszą jedynkę zapisu n (1101) przesuwasz na koniec → 1011 = 11.

Pytanie

n osób w kole, co druga zostaje wyeliminowana (idąc dookoła). Które miejsce przetrwa?

Najpierw spróbuj zgadnąć — dopiero potem odsłoń podpowiedź.

PodpowiedźPokaż

Zapisz n w systemie dwójkowym.

Pokaż rozwiązanie

Jeśli n = 2ᵐ + l, ocaleje miejsce 2l + 1.

Moment „aha”

Nazwa od historyka Józefa Flawiusza. Rozwiązanie ma zaskakująco prosty wzór binarny: pierwszą jedynkę zapisu n przesuwasz na koniec. Ładny splot rekurencji i systemu dwójkowego.

Powiązania

Matematyka przez wiekiścieżka

Ciekawa zagadka? Udostępnij.

Za darmo w NexTutor — rzuć komuś wyzwanie.

Uczysz? Umieść tę zagadkę na swojej stronie.

Darmowy widget — wklej na stronę szkoły, bloga lub notatki. Linkuje do pełnej wersji.

Uczysz w klasie albo korepetujesz? Prowadź uczniów w NexTutor →