100 prigionieri sono disposti in cerchio, numerati da 1 a 100. Il prigioniero 1 ha una spada e uccide il prigioniero 2, poi passa la spada al prigioniero 3. Il prigioniero 3 uccide il 4 e passa la spada al 5, e così via. Il processo continua finché rimane un solo prigioniero.
Quale prigioniero sopravvive?
Questo è il famoso problema di Josephus. Prova a trovare uno schema con numeri più piccoli (2, 4, 8, 16...). La formula coinvolge potenze di 2.
Sopravvive il prigioniero 73.
Per il problema di Josephus con n persone, trova la potenza di 2 più grande <= n. Per n=100, questa è 64 (2^6).
La formula è: J(n) = 2L + 1, dove n = 2^m + L
100 = 64 + 36, quindi L = 36
J(100) = 2(36) + 1 = 73