Il problema di Josephus

[dan952]

Supponiamo di avere un numero $N$ di soldati disposti in cerchio e numerati da $1$ a $N$, la regola è questa:
Ogni soldato, in senso orario, uccide il soldato (vivo) più vicino. Chi sopravvive?

Esempio: Con $N=5$ sopravvive il soldato n° 3

[axpgn]

Supponendo che si parta dal numero $1$ e si prosegua in ordine crescente , se $N=2^b$ allora il sopravvissuto è il numero $1$ altrimenti tra una potenza di due e l'altra avremo la sequenza crescente dei dispari ... per esempio

$((N=4,s=1),(N=5,s=3),(N=6,s=5),(N=7,s=7),(N=8,s=1))$

Cordialmente, Alex

[orsoulx]

Se si scrive N in base due si salverà il soldato n che, sempre in base due, è rappresentato dalla rotazione dei bit di N di una posizione verso sinistra: si shiftano i bit di un posto a sinistra e si trasferisce il bit più alto nella posizione 1.
Ciao

[dan952]

È un problema abbastanza noto per saperne di più Problema di Josephus

[axpgn]

Conoscevo già il problema originale, mi è capitato di leggerne altri, se li ritrovo li posto ... però mi pare che non esista una procedura generale (oltre questo caso s'intende) ... isn't it?

Cordialmente, Alex

[dan952]

Guarda qui [url=https://www.google.it/url?sa=t&source=web&rct=j&url=https://m.youtube.com/watch%3Fv%3DuCsD3ZGzMgE&ved=0ahUKEwjugIWFwqrVAhUCRhQKHd5vDukQyCkIHjAA&usg=AFQjCNHhXs1Dzr6AQ72tJ4rWsWoUGN3e5w]Numberphile-Josephus problem[/url]

[axpgn]

Due problemi:
- finché si tratta di leggere in inglese non c'è problema ma capire un discorso in inglese è un gran casino ... (eufemismo)
- il mio pc si rifiuta di farmi vedere i filmati di Youtube ...

quindi ero come il palo della banda dell'ortica: "perché vederci non vedeva un autobotte, però sentirci ghe sentiva un acident." (cit.Jannacci) ...

Comunque, son riuscito a vederlo ( ): in sostanza è arrivato alle conclusioni mie e di orsoulx ... cioè esiste un metodo quando il passo è $1$ ma quando è un generico $m$ ? Puoi solo contare ...

Tra l'altro il problema originale di Josephus richiede la decimazione ogni tre persone (ed è riportato da Hegesippus nel "De Bello Judaico"): in quale posizione deve mettersi Josephus per salvarsi ($41$ persone, si parte a contare da $1$, il terzo viene eliminato)

Cordialmente, alex

[dan952]

"axpgn":Puoi solo contare ...

O programmare...

[axpgn]

Se uno ne è capace ...

Dai, dimmi dove deve mettersi Josephus (nel problema originale ...)

[andomito]

"axpgn":Se uno ne è capace ...

Dai, dimmi dove deve mettersi Josephus (nel problema originale ...)

Se ho 41 decimandi, messi in cerchio, che uno sì, uno no prendono il coltello e ammazzano successivo girando in senso orario, detto numero 1 quello che inizia a contare (cui segue il 2 che ammazza il 3), alla fine ...

rimangono il numero 16 che conta e il numero 31 che prende il coltello e lo uccide, rimanendo ultimo superstite.

Dunque lo scaltro Josephus si metterà in quest'ultima posizione.

Purtroppo non ho una formula risolutiva, ci sono arrivato contando.