Dal WC con furore... 2 pile di gettoni...

[piever]

Davide e Federico stanno facendo un gioco:

ci sono 2 pile di gettoni, Davide inizia e a turno ciascun giocatore fa una mossa.

Una mossa consiste nel levare un po' di gettoni da una pila a scelta oppure nel levare un eguale quantita' di gettoni da entrambe le pile. Bisogna levare almeno un gettone per mossa. Perde chi non puo' piu' muovere.

Sia $ I\subset\mathbb{N}^2 $ l'insieme di configurazioni vincenti per Federico. (i due numeri naturali stanno l'uno per il numero di gettoni della prima fila e l'altro per il numero di gettoni della seconda fila)

Trovare una funzione $ F:\mathbb{N}\to I $ definita per ogni naturale e iniettiva, che puo' essere scritta usando solo le quattro operazioni e l'elevamento a potenza k-esima con $ k\in\mathbb{R} $

Esempio: $ F(n)=(1-\sqrt{2})^n+(1+\sqrt{2})^n;4n $ e' definita per ogni naturale e iniettiva e si scrive usando solo le quattro operazioni e l'elevamento a potenza k-esima con $ k\in\mathbb{R} $ pero' non va bene perche' $ F(0)=2;0 $ che e' decisamente una posizione vinta per Davide...

Buon lavoro.

Domanda bonus (che non ho ancora risolto): determinare tutte le confiugurazioni vinte per Federico (esiste un algoritmo per ricorsione, ma cercavo qualcosa di piu' efficace...)

ps: ditemi se non si capisce il testo del problema

[Simo_the_wolf]

Uhm certamente delle coppie che funzionanano sono:

$ (F_n +1 , F_{n+1} +2 ) $
$ (F_{2n}, F_{2n+1}) $

Dove $ F_n $ è l'ennesimo numero di Fibonacci.

Per trovarle tutte dobbiamo ricorrere alla rappresentazione in Fibonacci dei numeri naturali. Ogni numero naturale può essere espresso come somma di più Fibonacci distinti (non consecutivi, cioè se nella rappresentazione c'è $ F_k $ allora non ci sono nè $ F_{k+1} $ nè $ F_{k-1} $) in modo unico, e si vede facilmente per induzione. Ora se ad ogni naturale associamo la stringa di coefficienti da assegnare ai Fibonacci per fare lui: ad esempio 10=1*8+0*5+0*3+1*2+0*1 e quindi a 10 associo 10010 oppure 20 = 1*13+0*8+1*5+0*3+1*2+0*1 e quindi a 20 associo 101010.

Ora tutte e sole le coppie che fanno vincere Federico sono quelle avente per pila minore un numero che, nella sua rappresentazione in Fibonacci, finisce con un numero pari di zeri e per pila maggiore un numero che, nella rappresentazione in Fibonacci, è come quello della fila minore ma con l'aggiunta di uno zero.

Purtroppo questa è per ora solo una congettura... Ma pare funzionare!

[piever]

Uhm certamente delle coppie che funzionanano sono:

$ (F_n +1 , F_{n+1} +2 ) $
$ (F_{2n}, F_{2n+1}) $

Dove $ F_n $ è l'ennesimo numero di Fibonacci.

Right, io avevo pensato $ (F_n-2, F_{n+1}-3) $

Per trovarle tutte dobbiamo ricorrere alla rappresentazione in Fibonacci dei numeri naturali. Ogni numero naturale può essere espresso come somma di più Fibonacci distinti (non consecutivi, cioè se nella rappresentazione c'è $ F_k $ allora non ci sono nè $ F_{k+1} $ nè $ F_{k-1} $) in modo unico, e si vede facilmente per induzione. Ora se ad ogni naturale associamo la stringa di coefficienti da assegnare ai Fibonacci per fare lui: ad esempio 10=1*8+0*5+0*3+1*2+0*1 e quindi a 10 associo 10010 oppure 20 = 1*13+0*8+1*5+0*3+1*2+0*1 e quindi a 20 associo 101010.

Ebbene si, ma allora serve a qualcosa questo esercizio del Senior!

Ora tutte e sole le coppie che fanno vincere Federico sono quelle avente per pila minore un numero che, nella sua rappresentazione in Fibonacci, finisce con un numero pari di zeri e per pila maggiore un numero che, nella rappresentazione in Fibonacci, è come quello della fila minore ma con l'aggiunta di uno zero.

'azzo, complimenti!! Come diavolo ti e' venuta in mente una cosa simile???

Purtroppo questa è per ora solo una congettura... Ma pare funzionare!

Mi pare di aver trovato una dimostrazione. Lascio il tempo ad altri prima di postare.

[MindFlyer]

rappresentazione in Fibonacci

Rappresentazione di Zeckendorf, prego.

[Marco]

Purtroppo questa è per ora solo una congettura... Ma pare funzionare!

Funziona, ma è un po' noiosa da scrivere fino in fondo, a meno che non abbiate qualche idea migliore delle mie

Sia N un intero positivo. Allora se la scrittura in base fibonacci (s.b.f) [di Zeckendorf??] di N termina con un numero pari di 0, dico che N è un figlio. Altrimenti, e quindi termina con un numero di zeri dispari, allora dico che è un padre. 0 non è né padre, né figlio.

Io ho usato il seguente lemma.

Se ordiniamo la successione dei figli e dei padri, allora il k-esimo padre si ottiene aggiungendo k al k-esimo figlio.

Dimostrazione lunghetta e noiosa per induzione sul numero di cifre s.b.f.

Da lì a scrivere la strategia vincente il passo è breve:

(A,B) con A>=B è perdente sse è della forma (padre, figlio) [oppure la coppia banale (0,0)], che è il tuo Claim.

Infatti:

Se B è padre, tolgo gettoni da A per restare con (B, figlio di B) e vinco.
Se B è figlio e A > padre di B, allora lascio (padre di B, B) e vinco.
Se B è figlio e A < padre di B, allora sia k = A-B. Per il Lemma, la k-esima coppia padre-figlio è raggiungibile sottraendo lo stesso numero di gettoni.

Da qui, dimostrare che è vincente, è straight.

Notare anche che la strategia è sharp: la mossa vincente è sempre unica.

[Simo_the_wolf]

Se si fanno un po' di prove si arriva alla congettura (facilmente dimostrabile) che le coppie perdenti $ (a_i,b_i) $ con $ a_i>b_i $ e $ a_i<a_{i+1} $ sono tali che: $ a_i=b_i+i $ e gli insiemi $ A=\{a_i| i \in N_0\} $ e $ B=\{ b_i | i \in N_0 \} $ sono disgiunti e la loro unione è $ N_0 $.

Sapendo questo si può vedere che $ a_n = \lfloor n \phi \rfloor +n = \lfloor n \phi ^2 \rfloor $ e $ b_n = \lfloor n \phi \rfloor $. In questo modo, infatti, poichè $ \frac 1 {\phi} + \frac 1{\phi^2} =1 $ abbiamo che $ A $ e $ B $ sono disgiunti e la loro unione fa $ N $ (e abbiamo che $ a_n - b_n=n $ ).

Vi lascio come esercizio dimostrare che se $ \frac 1a + \frac 1b =1 $ con $ a,b>1 $ allora $ A=\{ \lfloor na \rfloor | n \in N_0\} $ e $ B=\{ \lfloor nb \rfloor | n \in N_0 \} $ sono disgiunti e la loro unione è $ N_0 $.