Problema di Giuseppe

Il problema di Giuseppe o la permutazione di Giuseppe è un problema di matematica collegato a un episodio autobiografico raccontato dallo storico ebreo Flavio Giuseppe nella sua opera Guerra giudaica (composta tra il 93 e il 94 d.C.). Nelle discipline contemporanee, il problema si inserisce nell'ambito degli algoritmi e delle strutture dati che gestiscono le conte nell'informatica teorica.^[1]

Il problema presenta $n$ persone disposte in circolo in attesa di un'esecuzione. Scelta una persona iniziale e un senso di rotazione, si saltano $k-1$ persone, raggiungendo così la $k$ -esima persona, che viene giustiziata ed eliminata dal cerchio; di nuovo si saltano $k-1$ persone e si giustizia la successiva $k$ -esima persona. Le esecuzioni proseguono e il cerchio si restringe sempre più, finché, conteggiando eventualmente più di una volta i singoli individui nel corso dei giri, la conta si riduce a una sola persona, la quale viene graziata. Dati $n$ e $k$ , si chiede di determinare la posizione iniziale del sopravvissuto all'interno del cerchio.

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

*Problema di Giuseppe*, rappresentazione grafica con valori $n=500$ e $k=6$

Soluzione

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

Nella trattazione matematica classica, $n$ indica il numero di persone nel cerchio iniziale e $k$ indica il "salto" per ogni passaggio, ossia $k-1$ persone vengono saltate e la successiva viene eliminata. Le persone nel cerchio sono numerate dalla posizione iniziale $1$ a quella finale $n$ .

Il caso con salto 2

Il problema è risolto esplicitamente nel caso in cui a turno ogni persona elimini la persona alla sua sinistra, ossia quando $k=2$ . Si ponga $f(n)$ la funzione che restituisce la posizione del sopravvissuto.

Nel primo giro, tutte le persone nelle postazioni con numeri pari vengono eliminate. Nel secondo giro vengono eliminate le nuove postazioni pari, calcolate come se non ci fosse stato il primo passaggio attorno al cerchio.

Se il numero iniziale era pari ( $n=2j$ ), allora la persona in posizione $x$ durante il secondo giro del cerchio era originariamente in posizione $2x-1$ . La persona $f(j)$ che sopravviverà era originariamente in posizione $2f(j)-1$ . Trattandosi della medesima persona che sopravvive a $f(n)$ , questo produce la seguente relazione di ricorrenza:

f(2j)=2f(j)-1.

Se il numero iniziale era dispari ( $n=2j+1$ ), l'eliminazione della persona in posizione 1 può essere considerata come un'esecuzione aggiuntiva alla fine del primo giro. Durante il secondo giro, la persona in posizione $x$ era originariamente in posizione $2x+1$ , il che produce la relazione di ricorrenza:

f(2j+1)=2f(j)+1.

Formula chiusa ed espressione binaria

Per calcolare rapidamente la soluzione del problema per $k=2$ senza dover reiterare la funzione ricorsiva, occorre esprimere il numero totale di persone $n$ nella forma $n=2^{m}+l$ , dove $2^{m}$ è la massima potenza di 2 minore o uguale a $n$ , mentre $l$ è il resto (assumendo che sia $0\leq l<2^{m}$ ). L'equazione esplicita per determinare la posizione esatta del sopravvissuto diventa pertanto:^[1]

f(n)=2l+1.

In ambito informatico, questa proprietà assume una forma matematicamente elegante se si sfrutta la codifica del sistema numerico binario. La posizione del sopravvissuto può essere calcolata istantaneamente prendendo la rappresentazione binaria di $n$ ed effettuando uno scorrimento ciclico a sinistra (left shift) di un singolo bit. Spostando il bit più significativo (il primo "1" a sinistra) all'estremità opposta della stringa binaria (come bit meno significativo), il numero decimale che si ottiene corrisponde esattamente alla posizione di salvezza.

Il caso generale (k > 2)

Per un valore generico e maggiore di due del salto $k$ , il problema viene comunemente affrontato tramite l'impiego della programmazione dinamica. L'algoritmo calcola la posizione sicura partendo dal caso base $f(1,k)=1$ ed estendendolo per generare la soluzione ricorsiva fino a $n$ tramite l'espressione:

f(n,k)=f(n-1,k)+k-1\mod n+1.

Questo approccio garantisce una soluzione calcolabile con una complessità temporale lineare pari a $O(n)$ .

Note

1 2 (EN) Ronald L. Graham, Donald E. Knuth, Oren Patashnik, 1.3 The Josephus Problem, in Concrete Mathematics: A Foundation for Computer Science, 2ª ed., Addison-Wesley, 1994, ISBN 978-0201558029.
↑ Flavio Giuseppe, Libro III, Capitolo 8, in Guerra giudaica, Fondazione Lorenzo Valla, 1993, ISBN 978-8804118237.

Bibliografia

(EN) Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2ª ed., Addison-Wesley, 1994, ISBN 978-0201558029.
Flavio Giuseppe, Guerra giudaica, Fondazione Lorenzo Valla, 1993, ISBN 978-8804118237.

Voci correlate

Collegamenti esterni

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

[ConcreteMath-1] 1 2 (EN) Ronald L. Graham, Donald E. Knuth, Oren Patashnik, 1.3 The Josephus Problem, in Concrete Mathematics: A Foundation for Computer Science, 2ª ed., Addison-Wesley, 1994, ISBN 978-0201558029.

[2] Flavio Giuseppe, Libro III, Capitolo 8, in Guerra giudaica, Fondazione Lorenzo Valla, 1993, ISBN 978-8804118237.

[1]

[2]