Matematykatrudny
Problem Józefa
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żUkryj
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.