Josephus Flavius uppgift

Problemet med Josephus Flavius är ett problem som ingår i ett av de tidiga verken om underhållande matematik (1612) av Bacher de Meziriac . Uppgiften är som följer: 41 krigare står i en cirkel, med början från den första krigaren dödar de var tredje. Frågan är var du behöver stå för att vara den sista överlevande. I en mer allmän formulering är n krigare inblandade, som räknas i en cirkel, och dödar varje m -te. Rubriken på problemet kommer från en berättelse som hände Flavius Josephus under judiska kriget .

Historik

Detta problem har varit känt sedan 1612, då den franske matematikern Basche publicerade detta problem i sin samling Problem es Plaisants . Handlingen i problemet är baserad på historien som beskrevs av Josephus Flavius i hans historiska verk " Det judiska kriget ".

Enligt denna berättelse gömde sig Josefus med sin avdelning på fyrtio män, efter Yodfats fall , i en grotta, men upptäcktes av romarna. Alla i avdelningen, förutom Joseph, valde att begå självmord snarare än att kapitulera. Joseph försökte avskräcka sina följeslagare från att begå självmord. Men de anklagade honom för feghet och ville döda deras befälhavare. Vidare skriver Joseph (på tal om sig själv i tredje person ):

Och i denna svåra situation lämnade Josef inte sin klokhet: i hopp om Guds barmhärtighet bestämde han sig för att riskera sitt liv och sa: ”Det var bestämt att dö, så låt oss överlåta åt lotten att bestämma vem som skulle döda vem. Den som lotten faller på kommer att dö i händerna på den bredvid, och sålunda kommer vi alla i sin tur att dö den ena från den andra och undvika behovet av att ta livet av oss; det kommer naturligtvis att vara orättvist om man, efter att de andra redan dött, ändrar sig och förblir vid liv. Genom detta förslag återvann han åter deras förtroende; övertala andra deltog han själv också med dem i lotten. Var och en som lotten föll på lät sig i sin tur frivilligt stickas till döds av en annan kamrat som följde honom, eftersom strax därefter även befälhavaren skulle dö, och döden tillsammans med Josef tycktes dem vara bättre än livet. Av en lyckosam slump, eller kanske av gudomlig predestination, var det Josef som förblev den siste med en till. Och eftersom han inte ville varken själv bli dödad genom lottdragning eller färga sina händer med en landsmans blod, övertalade han den senare att överlämna sig åt romarna och rädda hans liv.Josefus Flavius . Judiska kriget, bok 3, kapitel 8 , 7

I Basches problem kastar inte soldaterna lott utan står i en cirkel och dödar var tredje. I det här fallet har Joseph möjligheten att inte förlita sig på slumpen, men kommer garanterat att bli frälst. Bashe frågar var Joseph och hans kamrat ska stå för att bli de sista som dras [1] .

Problemet inspirerade Stanislav Ulam att skapa konceptet med ett lyckotal [1] .

Tricket "Love Ritual" [2] skapat av den spanska magikern Woody Aragon som visas av Penn och Teller [3] är baserat på lösningen av Joseph-problemet för . $m=2$

Återkommande relationer

Om lösningen av problemet för ett visst antal krigare är känd, kan den användas för att lösa problemet med ytterligare ett antal krigare.

För det har vi $m=2$

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

För det har vi $m=3$

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

Uppenbarligen, för det allmänna fallet kommer vi att ha

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

Det är möjligt att konstruera återkommande relationer som konvergerar mycket snabbare än linjära. Här är ett exempel på att lösa problemet med ett logaritmiskt antal rekursionssteg: $m=2$

k(n)={\begin{cases}1,&{\mbox{if }}n=1\\2k\left({\frac {n}{2}}\right)-1,& {\mbox{if }}n>1{\mbox{ jämn}}\\2k\left({\frac {n-1}{2}}\right)+1,&{\mbox{ if }}n >1{\mbox{ udda}}\end{cases}}

Stängd formel

När de är programmerade ger ovanstående återkommande relationer beräkningskomplexiteten och resp. Att erhålla en lösning i sluten form bör leda till algoritmer där beräkningskomplexiteten är minimal - , d.v.s. inte beror på och alls . (Längden på representationen av tal i talsystemet tas inte med i beräkningen). Konstruktionen av sådana formler är också mycket önskvärd för detta problem. $På)$ $O(\log n)$ $O(1)$ $n$ $m$

För det finns en enkel formel: $m=2$

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

Lösningar

Sök lösning

Överväg ytterligare två sätt att lösa problemet som inte förlitar sig på ovanstående formel. Trots att de är svårare att beräkna i termer av beräkningshastighet är algoritmen ändå mer beskrivande. Låt oss upprepa händelserna som ägde rum i legenden i RAM.

Sätt ett

Vi kommer att lagra i arrayen namnen (dvs. numren) på alla för närvarande levande krigare. Antalet personer skrevs i arrayelement från 0 till N - 1 (den här egenskapen kommer att användas för att ta resten). När krigaren dör kommer vi att ta bort honom från arrayen, och de som stod bakom honom kommer att "skiftas" ett element till vänster.

Observera att om vi redan har dödat L personer, så är M = N - L fortfarande vid liv. Låt oss bara (i det L:te steget) döda personen som registrerades i vår array i element nummer j (och flytta människor, vilket skrevs i arrayen i element från j + 1 till M ett element till vänster). Sedan måste nästa döda personen som är skriven i denna array i elementet med talet (j + k - 1) % M.

Metod två

Låt oss skaffa en array där vi kommer att markera döda krigare (det vill säga det i-te elementet lagrar om krigare i är vid liv eller inte). Anta att vi har M levande människor i det aktuella steget och krigare j dog i föregående steg. För att hitta nästa springer vi genom arrayen, räknar de levande och hoppar över de döda. Den som vi räknar k % M på måste dö härnäst. Efter N - 1 steg finns en person kvar.

Rekursiv lösning

Den enklaste simuleringen kör O( ). Med hjälp av ett segmentträd är det möjligt att utföra simuleringen i . Men låt oss försöka hitta ett mönster som uttrycker svaret på problemet (N,K) genom lösningen av de tidigare problemen. Med hjälp av simulering kommer vi att konstruera en tabell med värden, säg nedan. $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

Och här är följande regelbundenhet ganska tydligt synlig:

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

(här, indexering från en förstör elegansen i formeln något)

Så vi har hittat en lösning på Flavius Josephus-problemet som fungerar i iterationer. $PÅ)$

Exempel

För att i detalj förklara de möjliga situationer som kan uppstå under lösningen förenklar vi det ursprungliga problemet och överväger fall nr 1, dessutom minskar vi kretsen av soldater från fyrtioen (fyrtio soldater och Josef) till tio och antar det istället för var tredje soldat, varannan. Som ett resultat kommer vi att överväga kretsen av soldater som avbildas i figur 1.

Fig 1. Cirkel om 10 soldater, i vilken

måste "dö" varje sekund

Om du räknar från den 1:e soldaten i cirkeln, kommer ordningen för borttagning att vara följande: 2, 4, 6, 8, 10, 3, 7, 1, 9. Soldat nummer 5 - förblir i slutändan vid liv.

Stadierna för "förstörelsen" av soldater från cirkeln presenteras grafiskt i figurerna 2-4.

Fig 2. Första steget för borttagning	Fig 3. 2:a steget av borttagning	Fig 4. 3:e steget av borttagning

Överväg en specifik situation och bestäm resultaten med fördefinierade villkor. Uppgiften är att fastställa beroenden mellan parametrarna k, n (där n är antalet personer i cirkeln, k används för att bestämma varje k:te soldat att "utesluta" från cirkeln), och lösa problemet oavsett hur många soldater står i en cirkel. Låt oss försöka härleda allmänna formler för att lösa problemet med alla ingångsparametrar (värdena på k och n ges som indata). För att göra detta definierar vi funktionen F(n), där F(n) returnerar vinnarens nummer. Det första antagandet uppstår omedelbart att F(n) kan ligga inom F(n) = n / 2, vilket är sant för n = 10 eller n = 2. Men för n = 4 F(4) = 1, vilket bevisar felaktighet i resonemanget. Följande anmärkning från situationen ovan: det erhållna resultatet är ett udda tal, oavsett värdet på n, detta hände på grund av det faktum att under det första steget togs alla jämna nummer bort. Du bör också ta hänsyn till att för n = 1 F(1) = 1. Antag att det vid ingången finns soldater = 2n. Vad som återstår efter det första steget visas i fig. 5.

Ris. 5 - 1:a etappen med antalet soldater i cirkeln 2n

En liknande situation observeras för 2n − 1 soldater vid ingången (fig. 6). En korrigering införs dock - en minskning med en och en ökning av F (n) med 2 gånger.

Ris. 6. soldat i cirkel 2n - 1

Från vilken vi kan härleda formeln F(2n) = 2 F(n) − 1 (för alla n > 1). Tänk på fall #2, med hänsyn till det faktum att ingången är 2n + 1 antal soldater (det vill säga ett udda antal soldater). Efter att ha utfört det första steget av "uteslutningen" av soldater från cirkeln kommer något att erhållas, visat i fig. 7.

Ris. 7 - 1:a etappen med antalet soldater i cirkeln 2n + 1

Från vilken vi kan härleda formeln F(2n +1) = 2 F(n) + 1 (för alla n > 1). Låt oss sammanfatta alla betraktade situationer och skriva alla fall i form av ett system som låter oss bestämma värdet på funktionen F(n) - för alla värden på n:

Formlerna härledda ovan kan också användas för att lösa det ursprungliga problemet - Josephus. Nämligen: F(2 m + k) = 2k + 1 för alla m någon k.

Representerar lösningen för fallet att döda varannan via binär notation

Betrakta de binära representationerna av kvantiteterna n och F ( n ): , där var och en är 0 eller 1, och den mest signifikanta biten är 1. När vi minns att , får vi successivt: ${\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))

(eftersom ) $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}$

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

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

(sedan och ) Således har vi fått det $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}

dvs F ( n ) erhålls genom att cykliskt skifta den binära representationen av n till vänster med en position.

Anteckningar

↑ 1 2 Dowdy, James; Mays, Michael E. Josephus permutationer // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1989. - Oktober ( vol. 6 ). - S. 125-130 .
↑ Penn & Teller Fool Us - Kan du hitta kärleken? på YouTube 2016.
↑ Ricardo Teixeira, Jang-Woo Park. Ett innovativt korttrick som kombinerar klassiska koncept // Recreational Mathematics Colloquium VI G4G Europe. - 2019. - Januari. — S. 11 . Arkiverad från originalet den 18 augusti 2019.

Litteratur

M. A. Alekseev. Problem av Joseph Flavius // Empire of Mathematics. - 2001. - Nr 2 . - S. 22-28 .
Donald Knuth , Ronald Graham , Oren Patashnik . konkret matematik. Grunden för datavetenskap = konkret matematik. En stiftelse för datavetenskap . — M .: Mir ; Binom. 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

Josephus Flavius ​​uppgift