Úkol Josepha Flavia

Problém Josepha Flavia je problém zahrnutý v jednom z raných děl o zábavné matematice (1612) od Bachera de Meziriac . Úkol je následující: 41 válečníků stojí v kruhu, počínaje prvním válečníkem, zabijí každého třetího. Otázkou je, kde musíte stát, abyste přežili jako poslední. V obecnější formulaci jde o n válečníků, kteří se počítají v kruhu a zabíjejí každého m -tého. Název problému pochází z příběhu, který se stal Flaviovi Josephovi během židovské války .

Historie

Tento problém je znám již od roku 1612, kdy francouzský matematik Basche publikoval tento problém ve své sbírce Problem es Plaisants . Zápletka problému je založena na příběhu, který popsal Josephus Flavius ve svém historickém díle „ Židovská válka “.

Podle tohoto příběhu se Josephus se svým oddílem čtyřiceti mužů po pádu Yodfatu ukryl v jeskyni, ale byl objeven Římany. Všichni v oddíle, kromě Josepha, se raději rozhodli spáchat sebevraždu, než by se vzdali. Joseph se snažil odradit své společníky od sebevraždy. Obvinili ho však ze zbabělosti a chtěli svého velitele zabít. Dále Joseph (mluví o sobě ve třetí osobě ) píše:

A v této těžké situaci Josef neopustil svou opatrnost: v naději na Boží milosrdenství se rozhodl riskovat svůj život a řekl: „Bylo rozhodnuto zemřít, nechme tedy na losu, kdo koho zabije. Ten, na koho padne los, zemře rukou toho, kdo je vedle něj, a tak my všichni zase zemřeme jeden od druhého a vyhneme se nutnosti zabít se; bylo by samozřejmě nespravedlivé, když po smrti ostatních jeden změní názor a zůstane naživu. Tímto návrhem si opět získal jejich důvěru; přesvědčování ostatních, sám se s nimi také účastnil losu. Každý, na koho padl los, se zase dobrovolně nechal ubodat k smrti dalším soudruhem, který ho následoval, protože brzy nato měl zemřít i velitel a smrt spolu s Josefem se jim zdála lepší než život. Šťastnou náhodou, nebo možná božským předurčením, to byl Josef, kdo zůstal poslední s ještě jedním. A protože nechtěl, aby byl sám zabit losem, ani si neposkvrnil ruce krví krajana, přesvědčil tohoto krajana, aby se vzdal Římanům a zachránil si život.Josephus Flavius . Židovská válka, kniha 3, kapitola 8 , 7

V Bascheově problému vojáci nelosují , ale stojí v kruhu a zabíjejí každého třetího. V tomto případě má Joseph možnost nespoléhat na náhodu, ale zaručeně bude zachráněn. Bashe se ptá, kde by měl stát Joseph a jeho kamarád, aby byli vylosováni jako poslední [1] .

Tento problém inspiroval Stanislava Ulama k vytvoření konceptu šťastného čísla [1] .

Trik „Rituál lásky“ [2] vytvořený španělským mágem Woodym Aragonem , který ukázal Penn a Teller [3], je založen na řešení Josephova problému pro . $m=2$

Opakující se vztahy

Je-li známo řešení problému pro určitý počet válečníků, lze jej použít k vyřešení problému s dalším počtem válečníků.

Protože máme $m=2$

k(n)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1)+1)\mod {n},&{\ mbox{if }}n>1\end{cases}}

Protože máme $m=3$

k(n)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1)+2)\mod {n},&{\ mbox{if }}n>1\end{cases}}

Je zřejmé, že pro obecný případ budeme mít

\forall m>0:k(n,m)={\begin{cases}1,&{\mbox{if }}n=1\\1+(k(n-1,m)+m -1)\mod {n},&{\mbox{if }}n>1\end{cases}}

Je možné konstruovat rekurentní vztahy, které konvergují mnohem rychleji než lineární. Zde je příklad řešení problému s logaritmickým počtem kroků rekurze: $m=2$

k(n)={\begin{cases}1,&{\mbox{if }}n=1\\2k\left({\frac {n}{2}}\right)-1,& {\mbox{if }}n>1{\mbox{ even}}\\2k\left({\frac {n-1}{2}}\right)+1,&{\mbox{ if }}n >1{\mbox{ odd}}\end{cases}}

Uzavřený vzorec

Při naprogramování dávají výše uvedené rekurentní vztahy výpočetní náročnost resp . Získání řešení v uzavřené formě by mělo vést k algoritmům, ve kterých je výpočetní náročnost minimální - tedy nezávisí na a vůbec . (Délka zastoupení čísel v číselné soustavě se nebere v úvahu). Konstrukce takových vzorců je vysoce žádoucí i pro tento problém. $Na)$ $O(\log n)$ $O(1)$ $n$ $m$

Protože existuje jednoduchý vzorec: $m=2$

k(n)=2\cdot \left(n-2^{{\lpatro \log _{2}n\rpatro }}\vpravo)+1

Řešení

Řešení hledání

Zvažte další dva způsoby řešení problému, které se nespoléhají na výše uvedený vzorec. Navzdory tomu, že jsou z hlediska výpočetní rychlosti náročnější na výpočet, je algoritmus popisnější. Zopakujme si v RAM události, které se odehrály v legendě.

První cesta

Do pole uložíme jména (tj. čísla) všech aktuálně žijících válečníků. Počty osob byly zapsány v prvcích pole od 0 do N - 1 (tato vlastnost bude použita pro operaci odebrání zbytku). Když válečník zemře, odstraníme ho z pole a ti, kteří stáli za ním, budou „posunutí“ o jeden prvek doleva.

Všimněte si, že pokud jsme již zabili L lidí, pak jsou stále naživu M = N - L. Zabijme pouze (v L-tém kroku) osobu, která byla zaznamenána v našem poli v prvku číslo j (a přesuneme lidi, kteří byly zapsány do pole v prvcích od j + 1 do M o jeden prvek vlevo). Pak další musí zabít osobu, která je zapsána v tomto poli v prvku s číslem (j + k - 1) % M.

Metoda dva

Získáme pole, kde označíme mrtvé válečníky (to znamená, že i-tý prvek ukládá, zda válečník i žije nebo ne). Předpokládejme, že v současném kroku máme M živých lidí a válečník j zemřel v předchozím kroku. Abychom našli další, projdeme polem, budeme počítat živé a přeskakovat mrtvé. Jako další musí zemřít osoba, na kterou počítáme k % M. Po N - 1 kroku zůstane jedna osoba.

Rekurzivní řešení

Nejjednodušší simulace poběží O( ). Pomocí stromu segmentů je možné provést simulaci v . Zkusme však najít vzor, který vyjadřuje odpověď na úlohu (N,K) prostřednictvím řešení předchozích úloh. Pomocí simulace sestrojíme tabulku hodnot, řekněme, uvedenou níže. $N^2$ $O(NlogN)$

Таблица

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8

A zde je zcela jasně vidět následující pravidelnost:

joseph ( n , k ) = ( joseph ( n -1 , k ) + k - 1 ) % n + 1 ; joseph ( 1 , k ) = 1

(zde indexování od jedné mírně kazí eleganci vzorce)

Našli jsme tedy řešení problému Flavius Josephus, které funguje v iteracích. $NA)$

Příklad

Abychom podrobně vysvětlili možné situace, které mohou při řešení nastat, zjednodušíme původní problém a vezmeme v úvahu případ č. 1, navíc okruh vojáků zmenšíme z jednačtyřiceti (čtyřicet vojáků a Josef) na deset a předpokládáme, že že místo každého třetího vojáka každý druhý. V důsledku toho budeme uvažovat kruh vojáků znázorněný na obrázku 1.

Obr 1. Kruh 10 vojáků, ve kterém

musí "umřít" každou sekundu

Pokud počítáte od 1. vojáka v kruhu, pak pořadí odstraňování bude následující: 2, 4, 6, 8, 10, 3, 7, 1, 9. Voják číslo 5 - nakonec zůstane naživu.

Fáze „zničení“ vojáků z kruhu jsou graficky znázorněny na obrázcích 2-4.

Obr. 2. 1. krok odstranění	Obr. 3. 2. fáze odstraňování	Obr 4. 3. fáze vyjímání

Zvažte konkrétní situaci a určete výsledky pomocí předem definovaných podmínek. Úkolem je stanovit závislosti mezi parametry k, n (kde n je počet lidí v kruhu, k se používá k určení každého k-tého vojáka, kterého „vyloučí“ z kruhu), a vyřešit problém bez ohledu na to, kolik vojáci stojí v kruhu. Pokusme se odvodit obecné vzorce pro řešení problému s libovolnými vstupními parametry (hodnoty k an jsou uvedeny jako vstup). K tomu definujeme funkci F(n), kde F(n) vrací číslo vítěze. Okamžitě vyvstane první předpoklad, že F(n) může být v rámci F(n) = n / 2, což platí pro n = 10 nebo n = 2. Nicméně pro n = 4 F(4) = 1, což dokazuje, nesprávnost úvahy. Následující poznámka z výše uvažované situace: získaný výsledek je liché číslo, bez ohledu na hodnotu n, stalo se tak proto, že během 1. etapy byla odstraněna všechna sudá čísla. Měli byste také vzít v úvahu skutečnost, že pro n = 1 F(1) = 1. Za předpokladu, že na vstupu je vojáků = 2n. Co zbyde po 1. etapě je znázorněno na Obr. 5.

Rýže. 5 - 1. stupeň s počtem vojáků v kruhu 2n

Podobná situace je pozorována pro 2n − 1 vojáka na vstupu (obr. 6). Je však zavedena korekce - snížení o jednu a zvýšení F (n) o 2 krát.

Rýže. 6. voják v kruhu 2n - 1

Z čehož můžeme odvodit vzorec F(2n) = 2 F(n) − 1 (pro všechna n > 1). Uvažujme případ č. 2 s přihlédnutím k faktu, že zadání je 2n + 1 počet vojáků (tedy lichý počet vojáků). Po provedení 1. etapy „vyloučení“ vojáků z kruhu se něco získá, znázorněno na obr. 7.

Rýže. 7 - 1. stupeň s počtem vojáků v kruhu 2n + 1

Z čehož můžeme odvodit vzorec F(2n +1) = 2 F(n) + 1 (pro všechna n > 1). Shrňme všechny uvažované situace a zapišme všechny případy ve formě systému, který nám umožňuje určit hodnotu funkce F(n) - pro libovolné hodnoty n:

Vzorce odvozené výše lze také použít k řešení původního problému - Josephus. Konkrétně: F(2 m + k) = 2k + 1 pro libovolné m libovolné k.

Reprezentující řešení pro případ zabíjení každého 2. pomocí binárního zápisu

Uvažujme binární reprezentace veličin n a F ( n ): , kde každá je 0 nebo 1 a nejvýznamnější bit je 1. Připomeňme si , že postupně získáme: ${\displaystyle n=b_{m}\cdot 2^{m}+b_{m-1}\cdot 2^{m-1}+...+b_{1}\cdot 2+b_{0))$ $bi}$ $b_{m}$ $n=2^{m}+k$

{\displaystyle n=(1\,b_{m-1}...b_{1}b_{0})_{2))

{\displaystyle k=(0\,b_{m-1}...b_{1}b_{0})_{2))

(protože ) $k=n-2^{m}=2^{m}+b_{m-1}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2+b_{0} -2^{m}=0\cdot 2^{m}+b_{m-1}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2+b_{0}$

2k=(b_{m-1}\ldots b_{1}b_{0}0)_{2}

(protože ) $2k=2(b_{m-1}\cdot 2^{m-1}+b_{m-2}\cdot 2^{m-2}+\ldots +b_{1}\cdot 2+ b_{0})=b_{m-1}\cdot 2^{m}+b_{m-2}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2^{2} +b_{0}\cdot 2+0$

{\displaystyle 2k+1=(b_{m-1}\ldots b_{1}b_{0}1)_{2))

{\displaystyle F(n)=(b_{m-1}\ldots b_{1}b_{0}b_{m})_{2))

(od a ) Tak jsme získali, že $F(n)=2k+1$ $b_{m}=1$

F((b_{m}b_{m-1}\ldots b_{1}b_{0})_{2})=(b_{m-1}\ldots b_{1}b_{0} b_{m})_{2}

to znamená, že F ( n ) se získá cyklickým posouváním binární reprezentace n doleva o jednu pozici.

Poznámky

↑ 1 2 Dowdy, Jakub; Mays, Michael E. Josephus permutations // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1989. - Říjen ( 6. díl ). - S. 125-130 .
↑ Penn & Teller Oklamou nás – Dokážete najít lásku? na YouTube 2016.
↑ Ricardo Teixeira, park Jang-Woo. Inovativní karetní trik, který kombinuje klasické koncepty // Kolokvium z rekreační matematiky VI G4G Europe. - 2019. - leden. — Str. 11 . Archivováno z originálu 18. srpna 2019.

Literatura

M. A. Aleksejev. Problém Josepha Flavia // Říše matematiky. - 2001. - č. 2 . - S. 22-28 .
Donald Knuth , Ronald Graham , Oren Patashnik . konkrétní matematika. Základ informatiky = konkrétní matematika. Nadace pro informatiku . — M .: Mir ; Binomický. Knowledge Lab , 2006. - S. 703. - ISBN 5-94774-560-7 .

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8