Josephus Flavius feladata

Josephus Flavius problémája Bacher de Meziriac szórakoztató matematikáról szóló egyik korai munkájában (1612) szerepel . A feladat a következő: 41 harcos áll körbe, az első harcostól kezdve minden harmadikat megölnek. A kérdés az, hogy hol kell állnod ahhoz, hogy te legyél az utolsó túlélő. Egy általánosabb megfogalmazásban n harcos vesz részt, akiket körben számolnak , és minden m -edikben megölnek. A probléma címe egy történetből származik, amely Flavius Josephusszal történt a zsidó háború alatt .

Történelem

Ez a probléma 1612 óta ismert, amikor a francia matematikus, Basche közzétette ezt a problémát a Problem es Plaisants című gyűjteményében . A probléma cselekménye Josephus Flavius " A zsidó háború " című történelmi munkájában leírt történeten alapul .

A történet szerint Josephus negyvenfős különítményével Yodfat bukása után elbújt egy barlangban, de a rómaiak fedezték fel. A különítményben Joseph kivételével mindenki inkább az öngyilkosságot választotta a megadás helyett. Joseph megpróbálta eltántorítani társait az öngyilkosságtól. Azonban gyávasággal vádolták, és meg akarták ölni parancsnokukat. Továbbá József ( magáról beszél harmadik személyben ) ezt írja:

És ebben a nehéz helyzetben József nem hagyta el megfontoltságát: Isten irgalmának reményében úgy döntött, hogy kockára teszi az életét, és így szólt: „Úgy döntöttek, hogy meghalunk, ezért bízzuk a sorsra, hogy ki öljön meg kit. Akire a sors esik, az meghal a mellette lévő kezétől, és így mindannyian meghalunk egymástól, és elkerüljük, hogy megöljük magunkat; persze igazságtalan lesz, ha miután a többiek már meghaltak, valaki meggondolja magát és életben marad. Ezzel a javaslattal ismét visszanyerte bizalmukat; másokat rábeszélve ő maga is részt vett velük a sorsolásban. Mindenki, akire a sors esett, önként hagyta magát halálra szúrni egy másik, őt követő elvtárstól, mivel nem sokkal ezután a parancsnoknak is meg kellett halnia, és a halál Józseffel együtt jobbnak tűnt az életnél. Szerencsés véletlennek, vagy talán isteni eleve elrendelésnek köszönhetően József maradt az utolsó eggyel többel. És mivel nem akarta, hogy magát sorsolással öljék meg, vagy honfitársa vérével szennyezzék be a kezét, rávette az utóbbit, hogy adja meg magát a rómaiaknak és mentse meg az életét.Josephus Flavius . Zsidó háború, 3. könyv, 8. , 7. fejezet

Basche problémájában a katonák nem sorsot vetnek , hanem körbe állnak és minden harmadikat megölnek. Ebben az esetben Józsefnek lehetősége van arra, hogy ne a véletlenre hagyatkozzon, hanem garantáltan megmenekül. Bashe azt kérdezi, hol álljanak Joseph és bajtársa, hogy utoljára sorsolják ki őket [1] .

A probléma inspirálta Stanislav Ulamot a szerencseszám koncepciójának megalkotására [1] .

A "Szerelmi rituálé" [2] trükk, amelyet Woody Aragon spanyol bűvész készített, és amelyet Penn és Teller [3] mutat be, a Joseph probléma megoldásán alapul . $m=2$

Ismétlődő kapcsolatok

Ha egy bizonyos számú harcosra ismert a probléma megoldása, akkor azzal még egy számú harcossal megoldható a probléma.

Mert nekünk van $m=2$

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

Mert nekünk van $m=3$

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

Nyilvánvalóan az általános esetre lesz

\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}}

Lehetséges olyan ismétlődő kapcsolatokat építeni, amelyek sokkal gyorsabban konvergálnak, mint a lineárisak. Íme egy példa a probléma megoldására logaritmikus számú rekurziós lépéssel: $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}}

Zárt képlet

Programozáskor a fenti ismétlődési relációk adják meg a számítási bonyolultságot , ill. Ha egy megoldást zárt formában kapunk meg, akkor olyan algoritmusokhoz kell vezetni, amelyekben a számítási komplexitás minimális - , azaz egyáltalán nem függ és -től . (A számok számrendszerbeli ábrázolásának hosszát nem vesszük figyelembe). Ilyen képletek megalkotása ebben a problémában is nagyon kívánatos. $Tovább)$ $O(\log n)$ $O(1)$ $n$ $m$

Mert van egy egyszerű képlet: $m=2$

k(n)=2\cdot \left(n-2^{{\lfloor \log _{2}n\rfloor }}\right)+1

Megoldások

Keresési megoldás

Fontolja meg a probléma megoldásának két további módját, amelyek nem támaszkodnak a fenti képletre. Annak ellenére, hogy a számítási sebességet tekintve nehezebb kiszámítani, az algoritmus leíróbb. Ismételjük meg a RAM-ban a legendában lezajlott eseményeket.

Way one

A tömbben tároljuk az összes jelenleg élő harcos nevét (azaz számát). A személyek számát 0-tól N - 1-ig terjedő tömbelemekbe írtuk (ezt a tulajdonságot használjuk a maradék felvételéhez). Amikor a harcos meghal, eltávolítjuk a tömbből, és a mögötte állók egy elemmel balra „tolódnak”.

Vegyük észre, hogy ha már megöltünk L embert, akkor M = N - L még él. Csak (az L-edik lépésnél) öljük meg azt a személyt, akit a tömbünkben a j számú elemben rögzítettünk (és mozgassunk embereket, ami a tömbbe j + 1-től M-ig egy elemmel balra lévő elemekben írtak. Ezután a következőnek meg kell ölnie azt a személyt, aki ebbe a tömbbe van írva a (j + k - 1) % M számú elemben.

Második módszer

Vegyünk egy tömböt, ahol megjelöljük a halott harcosokat (azaz az i-edik elem azt tárolja, hogy i harcos él-e vagy sem). Tegyük fel, hogy az aktuális lépésnél M élő ember van, és j harcos meghalt az előző lépésben. A következő megtalálásához végigfutjuk a tömböt, megszámoljuk az élőket és kihagyjuk a holtakat. Legközelebb annak kell meghalnia, akire k % M-et számolunk. N - 1 lépés után egy személy marad.

Rekurzív megoldás

A legegyszerűbb szimuláció az O( ) futtatását végzi. Szegmensfa segítségével lehetőség van a szimuláció végrehajtására -ben . Próbáljunk azonban olyan mintát találni, amely az (N,K) feladatra a választ az előző feladatok megoldásán keresztül fejezi ki. Szimuláció segítségével összeállítunk egy értéktáblázatot, mondjuk az alábbiakban. $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

És itt egészen jól látható a következő szabályszerűség:

József ( n , k ) = ( József ( n -1 , k ) + k - 1 ) % n + 1 ; József ( 1 , k ) = 1

(itt az egytől való indexelés kissé elrontja a képlet eleganciáját)

Tehát találtunk egy megoldást a Flavius Josephus problémára, amely iterációkban működik. $TOVÁBB)$

Példa

A megoldás során felmerülő lehetséges helyzetek részletes ismertetése érdekében leegyszerűsítjük az eredeti problémát, és figyelembe vesszük az 1. esetet, sőt a katonák körét negyvenegyről (negyven katona és József) tízre csökkentjük, és feltételezzük, hogy hogy minden harmadik katona helyett minden második. Ennek eredményeként az 1. ábrán látható katonák körét vesszük figyelembe.

1. ábra 10 katonából álló kör, amelyben

minden másodpercben "meg kell halnia".

Ha az 1. katonától számítunk a körben, akkor az eltávolítás sorrendje a következő lesz: 2, 4, 6, 8, 10, 3, 7, 1, 9. Az 5-ös számú katona végül életben marad.

A katonák körből való „megsemmisítésének” szakaszait grafikusan a 2-4.

2. ábra Az eltávolítás 1. lépése	3. ábra Az eltávolítás 2. szakasza	4. ábra Az eltávolítás 3. szakasza

Vegyünk egy konkrét helyzetet, és határozzuk meg az eredményeket előre meghatározott feltételekkel. A feladat a k, n paraméterek közötti függőségek megállapítása (ahol n a körben tartózkodó személyek száma, a k segítségével határozzuk meg minden k-ik katonát, hogy „kizárjanak” a körből), és megoldjuk a feladatot, függetlenül attól, hogy hányan vannak. katonák körben állnak. Próbáljunk általános képleteket származtatni a probléma megoldására bármilyen bemeneti paraméterrel (k és n értékei bemenetként vannak megadva). Ehhez definiáljuk az F(n) függvényt, ahol F(n) a nyertes számát adja vissza. Az első feltevés azonnal felmerül, hogy F(n) lehet F(n) = n / 2-n belül, ami igaz n = 10 vagy n = 2 esetén. Azonban n = 4 esetén F(4) = 1, ami azt bizonyítja, hogy az érvelés helytelensége . A következő megjegyzés a fent vizsgált helyzetből: a kapott eredmény egy páratlan szám, függetlenül n értékétől, ez annak köszönhető, hogy az 1. szakasz során minden páros szám eltávolításra került. Azt is figyelembe kell venni, hogy n = 1 esetén F(1) = 1. Feltéve, hogy a bemeneten = 2n katonák vannak. Ami az 1. szakasz után marad, az az ábrán látható. 5.

Rizs. 5 - 1. szakasz a katonák létszámával a körben 2n

Hasonló helyzet figyelhető meg 2n − 1 katonánál a bemenetnél (6. ábra). Azonban bevezetünk egy korrekciót - eggyel csökkentjük és F (n) kétszeresére növeljük.

Rizs. 6. katona a 2n - 1 körben

Amiből levezethetjük az F(2n) = 2 F(n) − 1 képletet (minden n > 1-re). Tekintsük a 2. esetet, figyelembe véve azt a tényt, hogy a bemenet 2n + 1 számú katona (vagyis páratlan számú katona). A katonák körből való "kizárásának" 1. szakaszának végrehajtása után kapunk valamit, amit a 7. ábra mutat.

Rizs. 7 - 1. szakasz a katonák számával a 2n + 1 körben

Amiből levezethetjük az F(2n +1) = 2 F(n) + 1 képletet (minden n > 1-re). Foglaljuk össze az összes figyelembe vett helyzetet, és írjuk fel az összes esetet egy rendszer formájában, amely lehetővé teszi az F(n) függvény értékének meghatározását - n bármely értékére:

A fent levezetett képletek az eredeti probléma – Josephus – megoldására is alkalmazhatók. Nevezetesen: F(2 m + k) = 2k + 1 tetszőleges m bármely k esetén.

A minden 2. megölés esetének megoldását bináris jelöléssel ábrázolva

Tekintsük az n és F ( n ) mennyiségek bináris reprezentációit : , ahol mindegyik 0 vagy 1, és a legjelentősebb bit 1. Emlékezve arra , hogy egymás után megkapjuk: ${\displaystyle n=b_{m}\cdot 2^{m}+b_{m-1}\cdot 2^{m-1}+...+b_{1}\cdot 2+b_{0))$ $kettős}$ $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))

(mert ) $k=n-2^{m}=2^{m}+b_{m-1}\cdot 2^{m-1}+\ldots +b_{1}\cdot 2+b_{0} -2^{m}=0\cpont 2^{m}+b_{m-1}\cpont 2^{m-1}+\lpont +b_{1}\cdot 2+b_{0}$

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

(mert ) $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$

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))

( és óta ) Így azt kaptuk $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}

azaz F ( n )-t úgy kapjuk meg, hogy n bináris ábrázolását ciklikusan egy pozícióval balra toljuk.

Jegyzetek

↑ 1 2 Dowdy, James; Mays, Michael E. Josephus permutációk // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1989. - október ( 6. köt. ). - 125-130 . o .
↑ Penn & Teller átver minket – Megtalálod a szerelmet? a YouTube -on 2016.
↑ Ricardo Teixeira, Jang-Woo Park. Egy innovatív kártyatrükk, amely ötvözi a klasszikus fogalmakat // Rekreációs matematikai kollokvium VI G4G Europe. - 2019. - január. — 11. o . Archiválva az eredetiből: 2019. augusztus 18.

Irodalom

M. A. Alekszejev. Joseph Flavius problémája // A matematika birodalma. - 2001. - 2. sz . - S. 22-28 .
Donald Knuth , Ronald Graham , Oren Patashnik . konkrét matematika. Számítástudomány alapja = Concrete Mathematics. Számítástechnikai Alapítvány . — M .: Mir ; Binomiális. Knowledge Lab , 2006. - P. 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

Josephus Flavius ​​feladata