Problema de Flavio Josefo

Bust de Flavio Josefo quí va viure en la regió d'Aleixandria, en el primer sigle de l'era comuna. A dit personage se li atribuïx l'història que va donar orige al problema que du el seu nom.

Gràfic de l'evolució del problema de Flavio Josefo per a 500 persones i un valor de bot de 6. L'eix horisontal és el número de persona. L'eix vertical (de dalt cap a avall) és el temps (el número de cicle). Una persona viva és representada com un punt vert, una morta com un punt negre.

En matemàtiques i en les ciències de la computació, el problema de Flavio Josefo (o permutació de Josefo) és un problema teòric relacionat en un cert problema de tirar sòrts.

Hi ha gent de peu en un círcul a l'espera de ser eixecutada. El conte comença en un punt i direcció específica del círcul. En acabant de que s'hi haja salteado a un número determinat de persones, la següent persona és eixecutada. El procediment es repetix en les persones restants, a partir de la següent persona, que va en la mateixa direcció i ometent el mateix número de persones, fins que solament una persona permaneix i es lliura.

El problema (donat el número de persones, punt de partida, direcció, i el número de persones a botar) és elegir la posició en el círcul inicial per a evitar l'eixecució.

Història

El problema rep el nom de Flavio Josefo, historiador judeu que va viure en el I. Segons el relat del sege de Yodfat de Josefo, ell i els seus quaranta soldats varen quedar atrapats en una cova pels soldats romans. Varen elegir el suïcidi durant la captura, i varen establir un método per a suïcidar-se en série per sorteig. Josefo afirma que, per sòrt o, possiblement de la mà de Deu, ell i un atre home es varen mantindre fins al final i es varen rendir als romans en lloc de matar-se a sí mateixos. Esta és l'història donada en el llibre 3, capítul 8, partix 7 de La Guerra dels Judeus de Josefo (escritura de sí mateixa en tercera persona):

Els detalls del mecanisme utilisat en este ardit són prou vagos. Segons Dowdy i Mays, en 1612 Bachet va sugerir que el mecanisme específic va ser dispondre als hòmens en un círcul i contar de tres en tres per a determinar l'orde d'eliminació. Esta història s'ha repetit en freqüència i els detalls específics varien considerablement d'una font a una atra. Per eixemple, Herstein i Kaplansky (1974) tenen a Josefo i als seus 39 companyers colocats en círcul en cada sèptim home eliminat. Una història del problema es pot trobar en la carta de S. L. Zabell a l'editor de la Fibonacci Quarterly.

Josefo tenia un còmpliç; el problema era llavors trobar els llocs dels dos últims supervivents (de la conspiració dels quals asseguraria les seues supervivència). Alega que es va colocar junt a l'atre home en les posicions 31 i 16 respectivament.

Variants i generalisacions

Una versió migeval del problema de Josefo involucra a 15 cristians i a 15 turcs a bordo d'un barco en una tormenta que s'afonarà a menos que la mitat dels passagers siguen tirats per la broda. Els 30 es disponen en un círcul i cada novena persona ha de ser tirada al mar. ¿On deuen els cristians colocar-se per a garantisar que solament els turcs es llancen? En atres versions els rols dels turcs i els cristians estan intercanviats.

En Matemàtiques concretes: Una Fundació de Ciències Informàtiques, Graham, Knuth i Patashnik descriuen i estudien una variant "estàndart": determinen on es disponen els últims supervivents si hi ha n persones inicialment i cada segona persona (k menor o igual a 2) és eliminada.

Una generalisació del problema és la següent. Suponem que cada m-ésima persona serà eixecutada d'un grup de tamany n, en el qual la n-ésima persona és la supervivent. Si hi ha una adició de x persones al círcul, llavors el supervivent està en la (p + mx)-ésima posició si és menor o igual a (p + mx) − (n + x)