Problema di Giuseppe
Un antico dilemma di sopravvivenza che nasconde un'elegante struttura binaria.
La Storia e la Regola
Si narra che Flavio Giuseppe, durante l'assedio di Iotapata nel 67 d.C., si trovasse intrappolato in una grotta con 40 compagni. Decisero di suicidarsi pur di non cadere in mano ai Romani.
La regola era questa: stando in cerchio, si eliminava ogni K-esimo uomo. Giuseppe, volendo sopravvivere, calcolò rapidamente la posizione sicura per restare l'ultimo.
Se ci sono N soldati e il passo è K, dove dovresti sederti?
Il Trucco Matematico
Se il passo di eliminazione è K=2, esiste una formula magica basata sulle potenze di 2.
Se il numero totale è N = 2^m + L (dove L è il resto), la posizione vincente è 2L + 1.
In codice binario, basta spostare il primo bit (l'1 più a sinistra) alla fine del numero per ottenere la posizione vincente!