Јосифов проблем уреди

У рачунарству и математици Јосифов проблем^[1] или Јосифова пермутација је теоријски проблем везан за игре елиминације пребројавањем.
Људи стоје у кругу чекајући да буду елиминисани. Пребројавање почиње од некога из круга и наставља се у фиксном правцу(смеру). У сваком кораку један број особа бива прескочен а следећа особа бива елиминисана. Елиминација се наставља над преосталим особама чији број постаје све мањи и мањи све док не остане само једна особа. Задатак је да се изабере положај играча у првом кругу тако да тај играч избегне елиминацију тј., победи.

Историјат уреди

Проблем је назван по Јосифу Флавију, јеврејском историчару који је живео у првом веку. Према Јосифовом запису о опсади Јодфата, он је заједно са још 40 војника био заробљен у пећини чији су излаз блокирали Римљани. Изабрали су самоубиство уместо заробљеништва и одлучили да направе круг и да међусобно убијају сваког трећег. Јосиф тврди да су, срећом или можда уз Божију помоћ, он и још један човек једини преживели и предали се Римљанима.
Следи одломак из 3. књиге, 8. поглавља, 7. пасуса Јосифовог дела ‘’Јудејски рат’’(писаног у трећем лицу):
{{quotation|А како Јосифа и покрај тога очајног положаја није напуштала његова присебност, уздајући се у божију заштиту, стави свој живот на коцку па рече: "Пошто је закључено да се умре, то нека коцка одреди који ће сваки пут бити убијен од другога. Нека онај на кога падне коцка буде убијен од оних на које падне коцка после њега(поред њега). Тако ће сваког задесити иста судба а да ниједан не страда од своје руке. Јер не би било право да се после убиства другога неко покаје и спаси се." Овај предлог му врати поверење пошто је и он морао вући коцку. Чим би неко извукао коцку, драговољно је пуштао да га следећи убију свесни да ће тако и војсковођа одмах умрети. Јер су држали да им је смрт са Јосифом много милија од живота. Преостаде ипак он, сретним случајем или божијим одређењем, са још једним другом, па пошто га није ни коцка погодила, а није хтео ни да каља руке крвљу сународника, наговори и овога да се преда и да спаси живот. ^[2]

Решење уреди

У даљем тексту, $n$ означава почетни број људи у кругу, а $k$ означава индекс избаченог у сваком кораку, тј. $k-1$ људи се прескаче а $k$ -ти се елиминише. Људи у кругу су означени бројевима од $1$ до $n$ .

Случај k=2 уреди

Експлицитно ћемо решити проблем за случај када свака друга особа треба да буде елиминисана, односно $k=2$ (За општији случај, када $k\neq 2$ дајемо скицу решења испод). Решење проблема изражавамо рекурзивно. Нека $f(n)$ означава позицију преживелог у првобитном кругу. У првом кораку елиминишу се сви људи који су обележени парним бројевима. У другом кораку елиминише се сваки други, онда сваки четврти и тако даље као да није ни било првог корака.
Ако је првобитни број људи у кругу био паран онда особа која се нашла на позицији $x$ у другом кораку је првобитно била на позицији $2x-1$ (ма како да изаберемо $x$ ) Нека је $x=2j$ . Особа на позицији $f(j)$ која је прескочена, првобитно је била на позицији $2f(j)-1$ . Ово нам даје рекурентну везу:

f(2j)=2f(j)-1

:.

Ако је првобитни број људи у кругу био непаран, онда размишљамо овако: особа која је започела игру ће испасти на крају првог круга. И поново ће у другом кругу свака друга особа испасти, у трећем свака четврта, итд . У овом случају особа која је на позицији $x$ првобитно је била на позицији $2x+1$ . Ово нам даје рекурентну везу:

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

:

Када прикажемо табеларно вредности $n$ и $f(n)$ можемо уочити образац:

$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

Ово указује да је $f(n)$ систем растућих ланацa непарних бројева који се прекида са вредношћу $f(n)=1$ кад год је $n$ степен броја 2. Зато можемо одабрати $m,I$ тако да $n=2^{m}+l$ , и $0\leq l<2^{m}$ , тада је $f(n)=2l+1$ . Јасно је да вредности у табели задовољавају ову једначину. Или, може и овако да се каже: након што је $l$ људи избачено, остало је само њих $2^{m}$ и прелази се на $2l+1$ -вог. Он мора да преживи. Зато је $f(n)=2l+1$ . Следи доказ индукцијом.
Теорема: Ако $n=2^{m}+l$ , и $0\leq l<2^{m}$ , онда $f(n)=2l+1$ .
Доказ: Користимо потпуну индукцију по $n$ . Индукцијска претпоставка је тачна за $n=1$ . Разликујемо случајеве када је $n$ парно и када је непарно.
Ако је $n$ парно, бирамо $m_{1}$ , $l_{1}$ тако да $n/2=2_{1}^{m}+l_{1},0\leq l_{1}<2_{1}^{m}$ . Уочимо да $l_{1}=l/2$ . Имамо $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ , где друга једнакост следи на основу индуктивне претпоставке.
Ако је $n$ непарно, онда бирамо $m_{1},l_{1}$ тако да $(n-1)/2=2_{1}^{m}+l_{1},0\leq l_{1}<2_{1}^{m}$ . Уочимо да је сада $l_{1}=(l-1)/2$ . Имамо $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l-1$ , при чему друга неједнакост следи из индуктивне хипотезе. Овим је доказ завршен.
Можемо решити по $l$ да добијемо експлицитан израз за $f(n)$ :
$f(n)=2(n-2^{[}log_{2}(n)])+1$ .
Најелегантнији облик решења укључује бинарну репрезентацију величине $n$ : $f(n)$ се тада добија цикличним померањем у лево за једно место бинарне репрезентације броја $n$ . Ако је бинарна репрезентација $n=1b_{1}b_{2}\ldots b_{m}$ онда је решење дато са $f(n)=b_{1}b_{2}\ldots b_{m}1$ . Доказ следи из репрезентације $n$ као $2^{m}+l$ , или из претходног израза за $f(n)$

Општи случај уреди

Најлакши начин да се реши проблем у општем случају је да се користи динамичко програмирање извршавањем првог корака и коришћењем тог решења у преосталом проблему. Почев од првог, члан који се померио $s$ места од првог члана је на позицији $((s-1)modn)+1$ где је $n$ укупан број особа. Нека $f(n,k)$ oзначава позицију преживелог. Пошто се елиминише $k$ -та особа остаје нам $n-1$ особа у кругу, а поновно пребројавање почиње од члана који је у првобитном распореду био на позицији $(kmodn)+1$ . Позиција преживелог би била $f(n-1,k)$ ако би се почело од првог; како се почиње од $(kmodn)+1$ , ово даје следећу рекурентну везу:
$f(n,k)=((f(n-1,k)+k-1)modn)+1$ , уз услов $f(1,k)=1$ .
Што се може једноставније записати:
$g(n,k)=(g(n-1,k)+k)modn$ , уз услов $g(1,k)=0$
уколико бисмо нумерисали позиције од 0 до n-1.

Варијанте и генерализације уреди

Јосиф је имао помагача; у том случају проблем се састоји у томе да се погодно одаберу места за последњу двојицу преживелих(чија би завера осигурала њихово преживљавање). Показује се да је услов за то да један од њих буде на $16$ -том а други на $31$ -вом месту.^[3] Уопштење овог процеса је следеће. Претпостављамо да ће свака $m$ -та особа бити елиминисана од њих $n$ , a да је $p$ -та особа преживела елиминацију. Ако се дода још $x$ људи, онда ће позиција преживелог бити $p+mx$ -та, уколико је $p+mx\leq n+x$ . Ако је $x$ најмањи број такав да је $(p+mx)>(n+x)$ , тада је позиција преживелог $(p+mx)-(n+x)$ ^[4] .
Још једна варијанта је да се уместо елиминације фиксираног члана у сваком кораку, елиминише у првом кораку сваки други, у другом сваки трећи, итд , $k$ -ти, док год има смисла (Јосифово сито)^[5].

Проширење Јосифовог проблема уреди

Дефиниција проблема: Нека је $n$ особа нумерисано од $1$ до $n$ у кругу. Елиминише се свака друга особа од две. За дато $n$ наћи која ће особа бити елиминисана $x$ -та^[6] .

Белешке уреди

^ https://en.wikipedia.org/wiki/Josephus_problem
^ Флавије, Јосиф (1967). Јудејски рат. Просвета. (Превeo са латинског Душан Глумац)
^ Rouse Ball, W. W. (1896). Mathematical Recreations and Essays (2nd изд.). Macmillan. Приступљено 1. 8. 2015.
^ Robinson, W. J. (1960). „The Josephus Problem”. The Mathematical Gazette. 44 (347): 47—52. doi:10.2307/3608532. Приступљено 1. 8. 2015.
^ https://oeis.org/A000960
^ Armin Shams-Baragh Formulating The Extended Josephus Problem.

Литература уреди

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). „Chapter 14: Augmenting Data Structures”. Introduction to Algorithms (Second изд.). MIT Press and McGraw-Hill. стр. 318. ISBN 0-262-03293-7.

Спољашње везе уреди

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

[josifus01-1] ttps://en.wikipedia.org/wiki/Josephus_problem

[Josif1967-2] Флавије, Јосиф (1967). Јудејски рат. Просвета. (Превeo са латинског Душан Глумац)

[Ball1896-3] Rouse Ball, W. W. (1896). Mathematical Recreations and Essays (2nd изд.). Macmillan. Приступљено 1. 8. 2015.

[Robinson1960-4] Robinson, W. J. (1960). „The Josephus Problem”. The Mathematical Gazette. 44 (347): 47—52. doi:10.2307/3608532. Приступљено 1. 8. 2015.

[A000960-5] ttps://oeis.org/A000960

[6] Armin Shams-Baragh Formulating The Extended Josephus Problem.

[1]

[2]

[3]

[4]

[5]

[6]