Problema di Giuseppe

Il problema di Giuseppe o la permutazione di Giuseppe è un problema di matematica collegato ad un episodio autobiografico raccontato dallo storico ebreo Flavio Giuseppe nella sua opera Guerra giudaica (composta tra il 93 e il 94 d.C.). In tempi successivi il problema si inserisce nell'ambito degli algoritmi che gestiscono le conte in ambito informatico.

Interpretazione di Claude-Gaspard Bachet de Méziriac del Problema di Giuseppe con 41 soldati (${\displaystyle n=41}$) e una uccisione ogni 3 soldati (${\displaystyle k=3}$). La progressione temporale avviene lungo la spirale e i punti verdi indicano i soldati ancora in vita, i punti grigi i soldati morti e le croci rosse le uccisioni. L'immagine mostra che i soldati nelle postazioni 16 e 31 sono gli ultimi a rimanere in vita. Se la progressione continuasse (16-31-16) rimarrebbe in vita solo il soldato nella postazione 31.

Il problema presenta ${\displaystyle n}$ persone disposte in circolo in attesa di una esecuzione. Scelta una persona iniziale e un senso di rotazione, si saltano ${\displaystyle k-1}$ persone, raggiungendo così la ${\displaystyle k}$-esima persona, che viene giustiziata ed eliminata dal cerchio; di nuovo si saltano ${\displaystyle k-1}$ persone e si giustizia la ${\displaystyle k}$-esima persona. Le esecuzioni proseguono e il cerchio si restringe sempre più, finché non rimangono dapprima ${\displaystyle k-1}$ persone che in seguito, conteggiando eventualmente più di una volta i singoli individui nel corso della scelta del soggetto da eliminare, sono ridotte a una sola persona, la quale viene graziata. Dati ${\displaystyle n}$ e ${\displaystyle k}$, si chiede di determinare la posizione del sopravvissuto all'interno del cerchio iniziale.

Il problema prende il nome da Flavio Giuseppe, uno storico ebreo vissuto nel primo secolo. Secondo il resoconto di Giuseppe dell'assedio di Iotapata, lui e i suoi 40 soldati furono intrappolati in una grotta dai soldati romani. Essi decisero di suicidarsi piuttosto che venire catturati e impostarono un metodo seriale per commettere un omicidio-suicidio per estrazione a sorte.

Problema di Giuseppe, rappresentazione grafica con valori ${\displaystyle n=500}$ e ${\displaystyle k=6}$

Variante con ${\displaystyle n=30}$ e ${\displaystyle k=9}$

Soluzione

Penultimi (rosa) e ultimi (blu) sopravvissuti nel problema di Giuseppe per gruppi di dimensione ${\displaystyle n}$ con "salti" di dimensione ${\displaystyle k}$. Allargando l'immagine e passando sopra con il cursore ai valori ottenuti è possibile vedere la sequenza completa delle eliminazioni per ogni coppia di ${\displaystyle n}$ e ${\displaystyle k}$.

Nella trattazione seguente, ${\displaystyle n}$ indica il numero di persone nel cerchio iniziale e ${\displaystyle k}$ indica il "salto" per ogni passaggio, ossia ${\displaystyle k-1}$ persone vengono saltate e il successivo viene eliminato. Le persone nel cerchio sono numerate dalla posizione iniziale 1 a quella finale ${\displaystyle n}$ (il conteggio è inclusivo per gli estremi).

Il caso con salto 2

Il problema è risolto esplicitamente quando a turno ogni persona uccide la persona alla sua sinistra o destra, ossia quando ${\displaystyle k=2}$. Poniamo ${\displaystyle f(n)}$ la funzione della posizione del sopravvissuto, quando vi sono ${\displaystyle n}$ persone e ${\displaystyle k=2}$.

Nel primo passaggio tutte le persone nelle postazioni con numeri pari muoiono. Nel secondo passaggio muoiono le nuove postazioni pari, come se non ci fosse stato il primo passaggio intorno al cerchio.

Se il numero iniziale era pari, allora la persona in posizione ${\displaystyle x}$ durante il secondo passaggio del cerchio era originariamente in posizione ${\displaystyle 2x-1}$ (per ogni valore di ${\displaystyle x}$). Ponendo ${\displaystyle n=2j}$, la persona in ${\displaystyle f(j)}$ che sopravviverà era originariamente in posizione ${\displaystyle 2f(j)-1}$. Trattandosi sempre della stessa persona che sopravvive a ${\displaystyle f(n)}$, questo produce la relazione di ricorrenza:

${\displaystyle f(2j)=2f(j)-1.}$

Se il numero iniziale fosse dispari, quella della persona in posizione 1 può essere considerata come morte aggiuntiva alla fine del primo passaggio attorno al cerchio. Ancora una volta, durante la seconda volta intorno al cerchio, la nuova seconda persona muore, quindi la nuova quarta persona, ecc. In questo caso, la persona in posizione ${\displaystyle x}$ era originariamente in posizione ${\displaystyle 2x+1}$ e ciò produce la relazione di ricorrenza:

${\displaystyle f(2j+1)=2f(j)+1.}$

Collegamenti esterni

• (EN) Eric W. Weisstein, Josephus Problem, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica