[tex]n[/tex] persone sono seduto in cerchio, numerate consecutivamente da [tex]1[/tex] a [tex]n[/tex] in senso orario.
Iniziando con la persona numero [tex]2[/tex], rimuoviamo una persona si ed una no, procedendo in senso orario.
Per esempio, se [tex]n=6[/tex], le persone sono rimosse nell'ordine ordine [tex]2,4,6,3,1[/tex], e l' ultima persona rimasta è la numero [tex]5[/tex].
Sia [tex]j(n)[/tex] l' ultima persona rimasta.
Trovare un modo per calcolare [tex]j(n)[/tex] per ogni intero positivo [tex]n>1[/tex].
Bonus question: Come prima, ma si sceglie una persona a caso e se ne rimuove una ogni [tex]k-1[/tex], con [tex]k>2[/tex].
p.s. Il cerchio si stringe dopo ogni iterazione.
Problema di Gi.
Re: Problema di Gi.
Bello , lo hai inventato tu ?
Re: Problema di Gi.
No, fa parte del folklore olimpico, il titolo è un gioco di parole basato sul nome del vero "autore del problema" 
La parte principale non è complicata: è sufficiente sporcarsi un poco le mani (i.e. provare qualche caso) e notare un certo pattern.
La parte principale non è complicata: è sufficiente sporcarsi un poco le mani (i.e. provare qualche caso) e notare un certo pattern.
Re: Problema di Gi.
Premetto che non sono pratico di definizioni tecniche e che questa soluzione, che in teoria dovrebbe funzionare, è particolarmente intorcolata.
scriviamo ogni numero come [tex]2^x + y[/tex] dove [tex]y[/tex] è il minor numero possibile non negativo (ad esempio scrivendo [tex]10[/tex] in questo modo si ottiene [tex]2^3+2[/tex], scrivendo [tex]19[/tex] otteniamo [tex]2^4+3[/tex], ecc....). Ora [tex]j(n)[/tex] dovrebbe essere uguale a [tex]2y+1[/tex].
Sicuramente c'è una soluzione più elegante ma per ora è l'unica che son riuscito a cavar fuori...
...
scriviamo ogni numero come [tex]2^x + y[/tex] dove [tex]y[/tex] è il minor numero possibile non negativo (ad esempio scrivendo [tex]10[/tex] in questo modo si ottiene [tex]2^3+2[/tex], scrivendo [tex]19[/tex] otteniamo [tex]2^4+3[/tex], ecc....). Ora [tex]j(n)[/tex] dovrebbe essere uguale a [tex]2y+1[/tex].
Sicuramente c'è una soluzione più elegante ma per ora è l'unica che son riuscito a cavar fuori...
...Re: Problema di Gi.
Presumo la soluzione proposta sia per il quesito principale.
Come valori numerici ci siamo, ma senza la soluzione completa non posso giudicare la bontà del procedimento.
La mia soluzione passa per un fatto facilmente notabile sporcandosi le mani.
Sotto spoiler ti lascio una "tabella" di un po' di valori di [tex]j(n)[/tex] che calcolai a suo tempo, noti qualcosa?
Come valori numerici ci siamo, ma senza la soluzione completa non posso giudicare la bontà del procedimento.
La mia soluzione passa per un fatto facilmente notabile sporcandosi le mani.
Sotto spoiler ti lascio una "tabella" di un po' di valori di [tex]j(n)[/tex] che calcolai a suo tempo, noti qualcosa?
Testo nascosto:
Re: Problema di Gi.
Io ho ragionato basandomi su come rendere sotto formula il processo di "eliminazione dei numeri"...per logica il parret dovrebbe essere che partendo dalla potenza di due( le quali hanno i valori di [tex]j(n)[/tex] pari a [tex]1[/tex] ) [tex]j(n)[/tex] sono uguali ai numeri dispari in ordine crescente fino alla potenza di 2 successiva, giusto?
Re: Problema di Gi.
Esatto, [tex]j(2^k)=1[/tex]
Riesci a dimostrarlo per induzione?
Hint pesanti, praticamente una soluzione guidata
Dunque, sia [tex]k[/tex] il massimo intero positivo tale che [tex]2^k \le n[/tex], allora [tex]j(n)=2(n-2^k)+1[/tex]
Ci manca ancora un pezzetto, ossia mostrare che [tex]j(n)=2h+1 \Rightarrow j(n+1)=2(h+1)+1[/tex], supposto [tex]n \not = 2^k-1[/tex], ma anche questo viene facilmente per induzione.
Riesci a dimostrarlo per induzione?
Hint pesanti, praticamente una soluzione guidata
Testo nascosto:
Dunque, sia [tex]k[/tex] il massimo intero positivo tale che [tex]2^k \le n[/tex], allora [tex]j(n)=2(n-2^k)+1[/tex]
Ci manca ancora un pezzetto, ossia mostrare che [tex]j(n)=2h+1 \Rightarrow j(n+1)=2(h+1)+1[/tex], supposto [tex]n \not = 2^k-1[/tex], ma anche questo viene facilmente per induzione.
Re: Problema di Gi.
1)Al primo giro rimango tutti i dispari, dunque numeri della forma [tex]2^1m+1[/tex], al secondo tutti quelli della forma [tex]2^2m+1[/tex], ovvero [tex]2^(1+1)m+1[/tex] e così via, ed è facile dimostrare per induzione che al [tex]Kesimo[/tex] giro di eliminazione rimangono i numeri della forma [tex]2^km+1[/tex]. Questo conferma inoltre il punto 2) in quanto 1 è l'unico numero che rimarrà indipendentemente dal variare di [tex]k[/tex] in quanto [tex]2^km+1[/tex] con [tex]m=0[/tex] è smpre uguale ad [tex]1[/tex].
Il punto 3) è facile da dimostrare in quanto se fosse inferiore rimarrebbero altri numeri, mentre non può essere superiore in quanto il numero massimo nel cerchio è [tex]2^k[/tex] e ad ogni giro si dimezza, e dunque dividendo il numero per [tex]2k[/tex] si ottiene 1
Nella seconda parte non mi è molto chiaro così intendi scrivendo [tex]h[/tex], ma forse mi son perso qualcosa io
Il punto 3) è facile da dimostrare in quanto se fosse inferiore rimarrebbero altri numeri, mentre non può essere superiore in quanto il numero massimo nel cerchio è [tex]2^k[/tex] e ad ogni giro si dimezza, e dunque dividendo il numero per [tex]2k[/tex] si ottiene 1
Nella seconda parte non mi è molto chiaro così intendi scrivendo [tex]h[/tex], ma forse mi son perso qualcosa io
Re: Problema di Gi.
L'algoritmo dato sopra utilizza implicitamente che ogni numero sputato fuori dalla funzione [tex]j(n)[/tex] è dispari, ma questo non possiamo darlo per scontato; allora dobbiamo dimostrare per induzione che [tex]j(n)=2h+1 \Rightarrow j(n+1)=2(h+1)+1[/tex], con [tex]n \not = 2^k-1[/tex] perché possiamo considerare la dimostrazione a "settori" (ossia, sappiamo [tex]j(2^k)=1[/tex], dunque dimostrando quello sopra siamo a posto fino a [tex]j(2^{k+1}-1)[/tex], ma [tex]j(2^{k+1})=1[/tex] quindi siamo a posto fino a [tex]j(2^{k+2}-1)[/tex], e così via).