Josifov problem

Josifov problem

U računarstvu i matematici Josifov problem ili Josifova permutacija je teorijski problem vezan za igre eliminacije prebrojavanjem.
Ljudi stoje u krugu čekajući da budu eliminisani. Prebrojavanje počinje od nekoga iz kruga i nastavlja se u fiksnom pravcu(smeru). U svakom koraku jedan broj osoba biva preskočen a sledeća osoba biva eliminisana. Eliminacija se nastavlja nad preostalim osobama čiji broj postaje sve manji i manji sve dok ne ostane samo jedna osoba. Zadatak je da se izabere položaj igrača u prvom krugu tako da taj igrač izbegne eliminaciju tj., pobedi.

Istorijat

Problem je nazvan po Josifu Flaviju, jevrejskom istoričaru koji je živeo u prvom veku. Prema Josifovom zapisu o opsadi Jodfata, on je zajedno sa još 40 vojnika bio zarobljen u pećini čiji su izlaz blokirali Rimljani. Izabrali su samoubistvo umesto zarobljeništva i odlučili da naprave krug i da međusobno ubijaju svakog trećeg. Josif tvrdi da su, srećom ili možda uz Božiju pomoć, on i još jedan čovek jedini preživeli i predali se Rimljanima.
Sledi odlomak iz 3. knjige, 8. poglavlja, 7. pasusa Josifovog dela ‘’Judejski rat’’(pisanog u trećem licu):
{{quotation|А како Јосифа и покрај тога очајног положаја није напуштала његова присебност, уздајући се у божију заштиту, стави свој живот на коцку па рече: "Пошто је закључено да се умре, то нека коцка одреди који ће сваки пут бити убијен од другога. Нека онај на кога падне коцка буде убијен од оних на које падне коцка после њега(поред њега). Тако ће сваког задесити иста судба а да ниједан не страда од своје руке. Јер не би било право да се после убиства другога неко покаје и спаси се." Овај предлог му врати поверење пошто је и он морао вући коцку. Чим би неко извукао коцку, драговољно је пуштао да га следећи убију свесни да ће тако и војсковођа одмах умрети. Јер су држали да им је смрт са Јосифом много милија од живота. Преостаде ипак он, сретним случајем или божијим одређењем, са још једним другом, па пошто га није ни коцка погодила, а није хтео ни да каља руке крвљу сународника, наговори и овога да се преда и да спаси живот.

Rešenje

U daljem tekstu, $n$ označava početni broj ljudi u krugu, a $k$ označava indeks izbačenog u svakom koraku, tj. $k-1$ ljudi se preskače a $k$-ti se eliminiše. Ljudi u krugu su označeni brojevima od $1$ do $n$.

Slučaj k=2

Eksplicitno ćemo rešiti problem za slučaj kada svaka druga osoba treba da bude eliminisana, odnosno $k=2$(Za opštiji slučaj, kada $k\neq 2$ dajemo skicu rešenja ispod). Rešenje problema izražavamo rekurzivno. Neka $f(n)$ označava poziciju preživelog u prvobitnom krugu. U prvom koraku eliminišu se svi ljudi koji su obeleženi parnim brojevima. U drugom koraku eliminiše se svaki drugi, onda svaki četvrti i tako dalje kao da nije ni bilo prvog koraka.
Ako je prvobitni broj ljudi u krugu bio paran onda osoba koja se našla na poziciji $x$ u drugom koraku je prvobitno bila na poziciji $2x-1$(ma kako da izaberemo $x$) Neka je $x=2j$. Osoba na poziciji $f(j)$ koja je preskočena, prvobitno je bila na poziciji $2f(j)-1$. Ovo nam daje rekurentnu vezu:

$f(2j)=2f(j)-1$:.

Ako je prvobitni broj ljudi u krugu bio neparan, onda razmišljamo ovako: osoba koja je započela igru će ispasti na kraju prvog kruga. I ponovo će u drugom krugu svaka druga osoba ispasti, u trećem svaka četvrta, itd . U ovom slučaju osoba koja je na poziciji $x$ prvobitno je bila na poziciji $2x+1$. Ovo nam daje rekurentnu vezu:

$f(2j+1)=2f(j)+1$:

Kada prikažemo tabelarno vrednosti $n$ i $f(n)$ možemo uočiti obrazac:

$n$			1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$			1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

Ovo ukazuje da je $f(n)$ sistem rastućih lanaca neparnih brojeva koji se prekida sa vrednošću $f(n)=1$ kad god je $n$ stepen broja 2. Zato možemo odabrati $m,I$ tako da $n=2^{m}+l$, i $0\leq l<2^{m}$, tada je $f(n)=2l+1$. Jasno je da vrednosti u tabeli zadovoljavaju ovu jednačinu. Ili, može i ovako da se kaže: nakon što je $l$ ljudi izbačeno, ostalo je samo njih $2^{m}$ i prelazi se na $2l+1$-vog. On mora da preživi. Zato je $f(n)=2l+1$. Sledi dokaz indukcijom.
Teorema: Ako $n=2^{m}+l$, i $0\leq l<2^{m}$, onda $f(n)=2l+1$.
Dokaz: Koristimo potpunu indukciju po $n$. Indukcijska pretpostavka je tačna za $n=1$. Razlikujemo slučajeve kada je $n$ parno i kada je neparno.
Ako je $n$ parno, biramo $m_{1}$,$l_{1}$ tako da $n/2=2_{1}^{m}+l_{1},0\leq l_{1}<2_{1}^{m}$. Uočimo da $l_{1}=l/2$. Imamo $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$, gde druga jednakost sledi na osnovu induktivne pretpostavke.
Ako je $n$ neparno, onda biramo $m_{1},l_{1}$ tako da $(n-1)/2=2_{1}^{m}+l_{1},0\leq l_{1}<2_{1}^{m}$. Uočimo da je sada $l_{1}=(l-1)/2$. Imamo $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l-1$, pri čemu druga nejednakost sledi iz induktivne hipoteze. Ovim je dokaz završen.
Možemo rešiti po $l$ da dobijemo eksplicitan izraz za $f(n)$:
$f(n)=2(n-2^{[}log_{2}(n)])+1$.
Najelegantniji oblik rešenja uključuje binarnu reprezentaciju veličine $n$: $f(n)$ se tada dobija cikličnim pomeranjem u levo za jedno mesto binarne reprezentacije broja $n$. Ako je binarna reprezentacija $n=1b_{1}b_{2}\ldots b_{m}$ onda je rešenje dato sa $f(n)=b_{1}b_{2}\ldots b_{m}1$. Dokaz sledi iz reprezentacije $n$ kao $2^{m}+l$, ili iz prethodnog izraza za $f(n)$

Opšti slučaj

Najlakši način da se reši problem u opštem slučaju je da se koristi dinamičko programiranje izvršavanjem prvog koraka i korišćenjem tog rešenja u preostalom problemu. Počev od prvog, član koji se pomerio $s$ mesta od prvog člana je na poziciji $((s-1)modn)+1$ gde je $n$ ukupan broj osoba. Neka $f(n,k)$ označava poziciju preživelog. Pošto se eliminiše $k$-ta osoba ostaje nam $n-1$ osoba u krugu, a ponovno prebrojavanje počinje od člana koji je u prvobitnom rasporedu bio na poziciji $(kmodn)+1$. Pozicija preživelog bi bila $f(n-1,k)$ ako bi se počelo od prvog; kako se počinje od $(kmodn)+1$, ovo daje sledeću rekurentnu vezu:
$f(n,k)=((f(n-1,k)+k-1)modn)+1$, uz uslov $f(1,k)=1$.
Što se može jednostavnije zapisati:
$g(n,k)=(g(n-1,k)+k)modn$, uz uslov $g(1,k)=0$
ukoliko bismo numerisali pozicije od 0 do n-1.

Varijante i generalizacije

Josif je imao pomagača; u tom slučaju problem se sastoji u tome da se pogodno odaberu mesta za poslednju dvojicu preživelih(čija bi zavera osigurala njihovo preživljavanje). Pokazuje se da je uslov za to da jedan od njih bude na $16$-tom a drugi na $31$-vom mestu. Uopštenje ovog procesa je sledeće. Pretpostavljamo da će svaka $m$-ta osoba biti eliminisana od njih $n$, a da je $p$-ta osoba preživela eliminaciju. Ako se doda još $x$ ljudi, onda će pozicija preživelog biti $p+mx$-ta, ukoliko je $p+mx\leq n+x$. Ako je $x$ najmanji broj takav da je $(p+mx)>(n+x)$, tada je pozicija preživelog $(p+mx)-(n+x)$ .
Još jedna varijanta je da se umesto eliminacije fiksiranog člana u svakom koraku, eliminiše u prvom koraku svaki drugi, u drugom svaki treći, itd , $k$-ti, dok god ima smisla (Josifovo sito).

Proširenje Josifovog problema

Definicija problema: Neka je $n$ osoba numerisano od $1$ do $n$ u krugu. Eliminiše se svaka druga osoba od dve. Za dato $n$ naći koja će osoba biti eliminisana $x$-ta .

Literatura

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). „Chapter 14: Augmenting Data Structures”. Introduction to Algorithms (Second izd.). MIT Press and McGraw-Hill. str. 318. ISBN 0-262-03293-7. CS1 održavanje: Višestruka imena: spisak autora (veza)

Spoljašnje veze

• Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n^th out of 50 (maximum).
• Josephus Problem at the MathWorld encyclopedia