Sarcina lui Josephus Flavius

Problema lui Josephus Flavius  ​​este o problemă inclusă într-una dintre lucrările timpurii despre matematica distractivă (1612) de Bacher de Meziriac . Sarcina este următoarea: 41 de războinici stau într-un cerc, începând de la primul războinic, ucid fiecare treime. Întrebarea este unde trebuie să stai pentru a fi ultimul supraviețuitor. Într-o formulare mai generală, sunt implicați n războinici, care sunt numărați într-un cerc și ucid fiecare m -th. Titlul problemei provine dintr-o poveste care i s-a întâmplat lui Flavius ​​​​Josephus în timpul războiului evreiesc .

Istorie

Această problemă este cunoscută încă din 1612, când matematicianul francez Basche a publicat această problemă în colecția sa Problem es Plaisants . Intriga problemei se bazează pe povestea descrisă de Josephus Flavius ​​în lucrarea sa istorică „ Războiul evreiesc ”.

Potrivit acestei povestiri, Josephus cu detașamentul său de patruzeci de oameni, după căderea lui Iodfat , s-a ascuns într-o peșteră, dar a fost descoperit de romani. Toți cei din detașament, cu excepția lui Joseph, au ales să se sinucidă mai degrabă decât să se predea. Joseph a încercat să-și descurajeze însoțitorii să se sinucidă. Cu toate acestea, l-au acuzat de lașitate și au vrut să-și omoare comandantul. Mai mult, Iosif (vorbind despre sine la persoana a treia ) scrie:

Și în această situație grea, Iosif nu și-a lăsat prudența: în nădejdea milei lui Dumnezeu, s-a hotărât să-și riște viața și a spus: „S-a hotărât să moară, așa că să lăsăm soțului să hotărască cine să omoare pe cine. Cel asupra căruia îi cade lotul va muri din mâna celui de lângă el și astfel vom muri la rândul nostru toți unul de celălalt și vom evita nevoia de a ne sinucide; va fi, desigur, nedrept dacă, după ce ceilalți au murit deja, unul se va răzgândi și va rămâne în viață. Prin această propunere, el le-a recăpătat încrederea; convingându-i pe alții, el însuși a participat împreună cu ei la lot. Fiecare asupra căruia a căzut sorțul, la rândul său, s-a lăsat de bună voie să fie înjunghiat până la moarte de un alt tovarăș care l-a urmat, pentru că curând după aceea avea să moară și comandantul, iar moartea împreună cu Iosif li s-a părut mai bună decât viața. Dintr-o întâmplare norocoasă, sau poate prin predestinare divină, Iosif a fost cel care a rămas ultimul cu încă unul. Și pentru că nu voia nici să fie ucis prin sorți, nici să-și păteze mâinile cu sângele unui compatriot, l-a convins pe acesta din urmă să se predea romanilor și să-și salveze viața.Josephus Flavius . Războiul Evreiesc, Cartea 3, Capitolul 8 , 7

În problema lui Basche, soldații nu trag la sorți , ci stau în cerc și ucid fiecare treime. În acest caz, Iosif are ocazia să nu se bazeze pe întâmplare, dar este garantat că va fi salvat. Bashe întreabă unde ar trebui să stea Iosif și tovarășul său pentru a fi ultimii care să fie atrași [1] .

Problema l-a inspirat pe Stanislav Ulam să creeze conceptul de număr norocos [1] .

Trucul „Love Ritual” [2] creat de magicianul spaniol Woody Aragon care este prezentat de Penn și Teller [3] se bazează pe soluția problemei Joseph pentru .

Relații recurente

Dacă se cunoaște soluția problemei pentru un anumit număr de războinici, atunci poate fi folosită pentru a rezolva problema cu încă un număr de războinici.

Căci avem

Căci avem

Evident, pentru cazul general vom avea

Este posibil să se construiască relații recurente care converg mult mai repede decât cele liniare. Iată un exemplu de rezolvare a problemei cu un număr logaritmic de pași recursivi:

Formula închisă

Când sunt programate, relațiile de recurență de mai sus dau complexitatea de calcul și respectiv. Obținerea unei soluții în formă închisă ar trebui să conducă la algoritmi în care complexitatea de calcul este minimă - , adică nu depinde de și deloc . (Lungimea reprezentării numerelor în sistemul numeric nu este luată în considerare). Construirea unor astfel de formule este foarte de dorit și pentru această problemă.

Căci există o formulă simplă:

Soluții

Caută soluție

Luați în considerare încă două moduri de a rezolva problema care nu se bazează pe formula de mai sus. În ciuda faptului că sunt mai dificil de calculat în ceea ce privește viteza de calcul, cu toate acestea, algoritmul este mai descriptiv. Să repetăm ​​în RAM evenimentele care au avut loc în legendă.

Primul drum

Vom stoca în matrice numele (adică numerele) tuturor războinicilor în viață. Numerele de persoane au fost scrise în elemente de matrice de la 0 la N - 1 (această proprietate va fi folosită pentru operația de preluare a restului). Când războinicul moare, îl vom elimina din matrice, iar cei care au stat în spatele lui vor fi „deplasați” cu un element la stânga.

Rețineți că, dacă am ucis deja L oameni, atunci M = N - L sunt încă în viață. Să omorâm doar (la pasul L-a) persoana care a fost înregistrată în matricea noastră în elementul numărul j (și să mutăm oamenii, care au fost scrise în tablou în elemente de la j + 1 la M un element la stânga). Apoi următorul trebuie să omoare persoana care este scrisă în această matrice în elementul cu numărul (j + k - 1) % M.

Metoda a doua

Să obținem o matrice în care vom marca războinicii morți (adică elementul i stochează dacă războinicul i este în viață sau nu). Să presupunem că avem M oameni vii la pasul curent și războinicul j a murit la pasul anterior. Pentru a-l găsi pe următorul, vom alerga prin matrice, numărând cei vii și sărind peste cei morți. Persoana pe care socotim k % M trebuie să moară în continuare. După N - 1 pas, o persoană va rămâne.

Soluție recursiva

Cea mai simplă simulare va rula O( ). Folosind un arbore de segment , este posibil să se efectueze simularea în . Totuși, să încercăm să găsim un model care exprimă răspunsul pentru problema (N,K) prin rezolvarea problemelor anterioare. Cu ajutorul simulării, vom construi un tabel de valori, să zicem, prezentat mai jos.

Таблица

	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

Și aici este destul de clar vizibilă următoarea regularitate:

iosif ( n , k ) = ( iosif ( n -1 , k ) + k - 1 ) % n + 1 ; Iosif ( 1 , k ) = 1

(aici, indexarea de la una strică ușor eleganța formulei)

Deci, am găsit o soluție la problema Flavius ​​​​Josephus care funcționează în iterații.

Exemplu

Pentru a explica în detaliu posibilele situații care pot apărea în timpul soluționării, simplificăm problema inițială și luăm în considerare cazul nr. 1, în plus, reducem cercul de soldați de la patruzeci și unu (patruzeci de soldați și Iosif) la zece și presupunem că în loc de fiecare al treilea soldat, în fiecare secundă. Ca rezultat, vom lua în considerare cercul de soldați reprezentat în Figura 1.

Fig 1. Cercul de 10 soldaţi, în care
trebuie să „moară” în fiecare secundă

Dacă numărați de la primul soldat din cerc, atunci ordinea de îndepărtare va fi următoarea: 2, 4, 6, 8, 10, 3, 7, 1, 9. Soldatul numărul 5 - rămâne în cele din urmă în viață.

Etapele „distrugerii” soldaților din cerc sunt prezentate grafic în figurile 2-4.

Fig 2. Primul pas de îndepărtare	Fig 3. Etapa a 2-a de îndepărtare	Fig 4. Etapa a 3-a de îndepărtare

Luați în considerare o situație specifică și determinați rezultatele utilizând condiții predefinite. Sarcina este de a stabili dependențele dintre parametrii k, n (unde n este numărul de oameni din cerc, k este folosit pentru a determina fiecare k-lea soldat să „exclude” din cerc) și să rezolve problema indiferent de câți soldații stau în cerc. Să încercăm să derivăm formule generale pentru rezolvarea problemei cu orice parametri de intrare (valorile lui k și n sunt date ca intrare). Pentru a face acest lucru, definim funcția F(n), unde F(n) returnează numărul câștigătorului. Prima presupunere apare imediat că F(n) poate fi în F(n) = n / 2, ceea ce este adevărat pentru n = 10 sau n = 2. Totuși, pentru n = 4 F(4) = 1, ceea ce demonstrează că incorectitudinea raționamentului. Următoarea remarcă din situația considerată mai sus: rezultatul obținut este un număr impar, indiferent de valoarea lui n, acest lucru s-a întâmplat datorită faptului că în prima etapă au fost eliminate toate numerele pare. Ar trebui să țineți cont și de faptul că pentru n = 1 F(1) = 1. Presupunând că la intrare sunt soldați = 2n. Ceea ce rămâne după prima etapă este prezentat în Fig. 5.

Orez. 5 - 1-a etapă cu numărul de soldați din cerc 2n

O situație similară se observă pentru 2n − 1 soldați la intrare (Fig. 6). Cu toate acestea, se introduce o corecție - o scădere de unu și o creștere a F (n) de 2 ori.

Orez. 6. soldat în cerc 2n - 1

Din care putem deriva formula F(2n) = 2 F(n) − 1 (pentru toate n > 1). Luați în considerare cazul #2, ținând cont de faptul că intrarea este 2n + 1 număr de soldați (adică un număr impar de soldați). După efectuarea primei etape a „excluderii” soldaților din cerc, se va obține ceva, prezentat în Fig. 7.

Orez. 7 - prima etapă cu numărul de soldați din cerc 2n + 1

Din care putem deriva formula F(2n +1) = 2 F(n) + 1 (pentru toate n > 1). Să rezumăm toate situațiile luate în considerare și să scriem toate cazurile sub forma unui sistem care ne permite să determinăm valoarea funcției F(n) - pentru orice valoare a lui n:

Formulele derivate mai sus pot fi aplicate și pentru a rezolva problema inițială - Josephus. Și anume: F(2 m + k) = 2k + 1 pentru orice k.

Reprezentând soluția pentru cazul uciderii fiecărui 2 prin notație binară

Se consideră reprezentările binare ale mărimilor n și F ( n ): , unde fiecare este 0 sau 1, iar bitul cel mai semnificativ este 1. Reamintind că , obținem succesiv:

(pentru ca )

(pentru ca )

(deoarece și ) Astfel, am obținut că

,

adică F ( n ) se obţine prin deplasarea ciclică a reprezentării binare a lui n la stânga cu o poziţie.

Note

1. ↑ 1 2 Dowdy, James; Mays, Michael E. Josephus permutări  //  Journal of Combinatorial Mathematics and Combinatorial Computing. - 1989. - Octombrie ( vol. 6 ). - P. 125-130 .
2. ↑ Penn & Teller Fool Us - Poți găsi dragostea? pe YouTube 2016.
3. ↑ Ricardo Teixeira, Parcul Jang-Woo. Un truc inovator de cărți care combină conceptele clasice  //  Colocviul de matematică recreațională VI G4G Europe. - 2019. - Ianuarie. — P. 11 . Arhivat din original pe 18 august 2019.

Literatură

• M. A. Alekseev. Problema lui Joseph Flavius  ​​​​// Imperiul matematicii. - 2001. - Nr. 2 . - S. 22-28 .
• Donald Knuth , Ronald Graham , Oren Patashnik . matematică concretă. Foundation of Computer Science = Concrete Mathematics. O fundație pentru informatică . — M .: Mir ; Binom. Knowledge Lab , 2006. - P. 703. - ISBN 5-94774-560-7 .