The Josephus Problem

[Gi.]

"Un gruppo di $n$ persone sono sedute in cerchio, numerate consecutivamente da $1$ a $n$ in senso orario.
Iniziando con la persona numero $2$, rimuoviamo una persona si ed una no, procedendo in senso orario. Per esempio, se $n=6$, le persone sono rimosse in ordine $2,4,6,3,1$,e l' ultima persona rimasta é la numero $5$. Sia $j(n)$ l' ultima persona rimasta.

Trovare un modo per calcolare $j(n)$ per ogni intero positivo $n>1$. "

Metto la mia soluzione nascosta

Testo nascosto:

Iniziamo sporcandoci un po' le mani (tralascio i "calcoli"):

$j(2)=1$
$j(3)=3$
$j(4)=1$
$j(5)=3$
$j(6)=5$
$j(7)=7$
$j(8)=1$
$j(9)=3$
$j(10)=5$
$j(11)=7$
$j(12)=9$
$j(13)=11$
$j(14)=13$
$j(15)=15$

Adesso si nota bene l' andazzo del problema: i $j(n)$ partono da $1$ e percorrono tutti i numeri dispari fino ad incontrare un numero in cui $j(n)=n$, dunque se riuscissimo a capire quando $j(n)=n$ avremmo (quasi) finito, ma questo é molto facile, sempre intuitivamente notiamo che $j(n)=n \iff n=2^k-1$. Con queste informazioni possiamo elaborare un metodo per il calcono di $j(n)$ preso un $n>1$ qualunque: individuiamo l' intervallo di potenze di due a cui togliamo uno in cui é compreso n $2^k-1 \le n \le 2^{k+1}-1$, a questo punto so che $j(2^k-1)=2^k-1$ per cui é sufficiente calcolare $n-(2^k-1)$ per individuare $j(n)$, infatti supponiamo che quel calcolo dia come risultato m, allora $j(n)$ sarà l' m-esimo numero positivo dispari.

Vi sembra corretta?
Ovviamente, provate a risolverlo prima di guardarla

[ma_go]

"Un gruppo di $n$ persone sono sedute in cerchio, numerate consecutivamente da $1$ a $n$ in senso orario.
Iniziando con la persona numero $2$, rimuoviamo ogni altra persona, procedendo in senso orario. Per esempio, se $n=6$, le persone sono rimosse in ordine $2,4,6,3,1$,e l' ultima persona rimasta é la numero $5$. Sia $j(n)$ l' ultima persona rimasta.

Trovare un modo per calcolare j(n) per ogni intero positivo $n>1$. "

quella in grassetto sembra una traduzione automatica dall'inglese "every other person", cioè "una persona sì e una persona no". sbaglio?
e quando dici "rimuoviamo una persona" intendi che poi si stringe anche il cerchio, giusto?

è possibile che la tua soluzione sia giusta (sembra nel giro giusto di idee, comunque), ma non vedo l'ombra di una dimostrazione, e vedo l'ombra minacciosa di un "intuitivamente", che un po' mi spaventa...

[Gi.]

[...]quella in grassetto sembra una traduzione automatica dall'inglese "every other person", cioè "una persona sì e una persona no". sbaglio?

Esattamente, ammetto di non aver mai incontrato questa espressione.
Correggo il testo.

Ed hai ragione anche sul fatto che non é presente l' ombra di una dimostrazione, infatti quello che mi ha guidato alla soluzione é stata l' osservazione di quei casi con cui ho preso confidenza con il problema, e mi rendo conto che é pericoloso: il pattern individuato potrebbe benissimo andare per un tot di numeri e poi cambiare completamente.
Provo a pensare ad una possibile dimostrazione, difatti il punto cruciale della soluzione è uno solo (la doppia freccia), dimostrato quello ho dimostrato anche il resto.

Testo nascosto:

Su due piedi direi che se $n$ é pari allora il numero $n$ viene eliminato "al primo giro", se $n$ é un dispari non della forma $2^k-1$ dopo il primo giro rimangono un numero dispari di termini, quindi $n$ viene eliminato al secondo, se invece $n$ é della forma $2^k-1$ dopo il primo giro rimangono un numero pari di termini, e non é difficile vedere che $n$ non verrà mai eliminato

p.s. Si, il cerchio si stringe dopo ogni giro.

[milizia96]

Perché invece non dimostri che

Testo nascosto:

$j(2^k)=1 \forall k$

(a me sembra molto più facile così...)

[toti96]

io questa ultima cosa la dimostrerei per induzione correggetemi se sbaglio. noto che con $ k=1 $ la tesi è evidente e $ j(2)=1 $. ora se suppongo la tesi vera per i numeri da $ 1 $ a $ k-1 $,devo dimostrarne la verità per $ j(2^k) $. ora ,per come è costruita $ j(n) $prima levo tutti i numeri pari che,in un numero della forma $ 2^k $, sono $ 2^{k-1} $. ora mi rimangono $ 2^{k-1} $ posti e riparto da $ 3 $ e quindi per ipotesi induttiva la tesi è dimostrata ..può essere giusta come cosa??

[Gi.]

Prendiamo un numero della forma $ n=2^k $

$ 1,2,3,4,5,... $

dopo il primo giro rimangono tutti i numeri della forma $ 2m+1 $

$ 1,3,5,7,... $

dopo il secondo giro rimangono i numeri della forma $ 2^2m+1 $

$ 1,5,9,13,... $

dopo il terzo quelli della forma $ 2^3m+1 $

...

dopo il $ k-esimo $ quelli della forma $ 2^km+1 $, ma $ 2^km\ge2^k $ (l' uguaglianza si ha per $ m=1 $, ma $ 2^k $ è già stato eliminato al primo giro), per cui l' unico numero che rimane è $ 1 $ ($ m=0 $).

In effetti dovrei anche dimostrare che vi possono essere $ k $ giri e che ad ogni turno rimangono numeri della forma $ 2^h+1 $ dove h è il numero del giro.

La prima è facile: all' inizio abbiamo $ 2^k $ numeri e ad ogni giro ne togliamo la metà, per arrivare ad un solo numero dobbiamo dividere per $ 2^k $ e sono esattamente $ k $ giri.

La seconda la farei per induzione sul numero di giri.
Diciamo $ g $ il numero del giro, è evidente che per $ g=1 $ la proposizione è vera, infatti rimangono i numeri dispari della forma $ 2m+1 $. Supponiamo ora di giungere al giro $ h $, dove per ipotesi induttiva i numeri che rimangono sono quelli della forma $ 2^hm+1 $, dunque al giro $ h+1 $ avremo

$ 1,2^h+1,2^{h+1}+1,2^h3+1,2^{h+1}2+1,... $

adesso sappiamo che uno viene saltato, dunque è evidente che rimangono tutti i numeri della forma $ 2^{h+1}m+1 $, per cui la proposizione è valida per ogni numero $ h $ appartenente ai naturali.

[toti96]

diciamo che provo a dare una risposta XD allora il modo da me trovato per calcolare $ j(n) $ è questo: detto $ k $ il più grande intero positivo tale per cui $ 2^k \leq n < 2^{k+1} $,allora $ j(n)=2(n-2^k)+1 $.la mia idea,ma non so quanto sia giusta,era di dimostrare la formula per induzione:
-Passo induttivo base,la tesi con $ n=2 $ è vera
-Passo induttivo,se supponiamo vera la tesi per i numeri da $ 2 $ a $ n $ lo è anche per $ n+1 $.io qui ho ragionato semplicemente così:per la definizione stessa della funzione in questione, togliamo all'inizio tutti i numeri pari e rimaniamo quindi con un numero di posti uguale a $ \displaystyle \frac {n+1}{2} $ o $ \displaystyle \frac {n+2}{2} $ a seconda che $ n+1 $ sia dispari o pari. ora per ipotesi per questi numeri la tesi funziona:mi basta parlare di numero di posti e non di numero vero e proprio in quanto il numero di posto non corrisponderà più al numero del posto stesso e poi "contare" i posti tenendo conto che se $ n+1 $ è pari devo partire a contare dall' $ 1 $ ed eliminare per primo il $ 3 $ mentre se $ n+1 $ è dispari parto con il contare da $ n+1 $ ed elimino per primo l'$ 1 $. faccio un esempio per rendere più chiara la cosa :con $ n+1=7 $,eliminando i numeri pari mi rimangono $ 7,1,3,5 $ in ordine che ricadono nel caso $ m=4 $.applicando la formula trovo che $ j(4)=1 $,il primo posto tra quelli che mi sono rimasti è il $ 7 $ e verificando è il risultato esatto.

[auron95]

Ho una mezza soluzione.... Dico mezza perchè sono riuscito a definire j(n) per ricorrenza, tuttavia non ho trovato una formula elegante (probabilmente dalla ricorrenza si può trovare la formula di toti96)

Ora distinguo due casi:
- n è pari $= 2k$
Dopo un giro mi ritrovo con una situazione del tipo $1,3,5,\dots,2k-1$ con quindi $k$ persone, e devo ricominciare dalla seconda (3). Se io avessi $1,2,3,\dots,k$ l'ultima persona sarebbe $j(k)$, ma siccome la $m$-esima rimasta non ha numero $m$ ma numero $2m-1$ (sono tutti i dispari), e $j(k)$ indica la posizione dell'ultima persona e non il suo numero, per passare da posizione a numero devo fare $j(2k)=2j(k)-1$. E questa è la ricorrenza per i dispari.
- n è dispari $= 2k+1$
Analogamente dopo un giro dovrò rimuovere la 1a dopo la 2k-esima, e poi avrò $3,5,7,\dots,2k+1$ e devo rimuovere la seconda tra i rimasti (questa volta la 5). Ragiono analogamente a sopra, ho $k$ persone e la $m$-esima ha numero $2m+1$, quindi $j(2k+1)=2j(k)+1$

Quindi posso definire la funzione così:
$\left\{\begin{array}l j(1)=1 \\ j(2n)= 2j(n)-1 \\ j(2n+1)= 2j(n)+1 \end{array}\right.$

Il fatto che che ogni termine dipenda dalla sua metà mi fa pensare alle potenze di 2, in effetti si vede in fretta per induzione che $j(2^0)=1$ (caso base) e $j(2^{k+1})=2j(2^k)-1=2-1=1$ (sfruttando $j(2^k)=1$ per ipotesi induttiva).
Adesso però non so più come continuare.... devo pensarci ancora su. Probabilmente quello che ho scritto è sostanzialmente la soluzione di toti96 scritta in altre parole, e a cui manca un pezzo...

[auron95]

Ideuzza un po' "campata per aria":

Sostituendo con la ricorrenza fino ad arrivare a $j(1)$ posso scrivere $j(n)=2(2(\dots (2(2(j(1))\pm 1) \pm 1) \dots) \pm 1) \pm 1$ dove i $\pm$ dipendono se uso la formula per i pari o per i dispari quando devo riferirmi alla metà, e questo lo posso vedere dalla scrittura binaria di n: ogni 1 corrisponde a un + e ogni 0 corrisponde a un - (il primo 1 corrisponde al + di $j(1)$, che ovviamente è sempre un + dato che i numeri non iniziano con o ). Ora se k è il numero di cifre posso scrivere, svolgendo le moltiplicazioni ho:
$\dots = 2^k \pm 2^{k-1} \pm \dots \pm 4 \pm 2 \pm 1$. Questa è simile alla conversione dalla scrittura binaria a quella decimale solo che qui, dove compare uno 0, invece di non aggiungere la potenza di 2 corrispondente, la tolgo. Quindi se a n tolgo tutte le potenze di 2 corrispondenti agli 0 ottengo $j(n)$. La somma di queste potenze è pari alla somma di tutte fino a $2^k$ (che è $2^{k+1}-1$) meno la somma di quelle corrispondenti agli 1, che dà ovviamente n.
Quindi ottengo $j(n)=n-((2^{k+1}-1)-n)=2n-2^{k+1}+1=2(n-2^k)+1$ che è quella trovata anche da toti. Perdonatemi se questa soluzione è arzigogolata e probabilmente non si capirà niente, anch'io mi chiedo come abbia fatto a venire la soluzione dopo tutti questi casini.....