Griglia fibonacciosa

[53thebest]

Dato un quadrato con $2^n$ x $2^n$ caselle vale la seguente proprieta': la casella $i,j$ e' dello stesso colore di $j,i+j$ (le righe e le colonne sono numerate da $0$ a $2^n -1$), dimostrare che il massimo numero di colori che posso usare e' $2^n$ (e lo e' esattamente).

[dario2994]

Non l'ho risolto ma è un dispiacere vederlo così nascosto dopo così poco tempo... è così faigo! Qundi UPPPPP

[dario2994]

Mi ci sono ampiamente sfondato... ma alla fine ho vinto io!!! E con che soddisfazione È proprio faigo!

Lemma di Cencio: Dato $n\ge 1$ intero vale $\displaystyle \upsilon_2\left(F_{3\cdot 2^n}\right)=n+2$
Siano $b,c$ le radici di $x^2-x-1=0$ ($b$ è quella paffuta!).
È un fatto stranoto che vale $\displaystyle F_n=\frac{b^n-c^n}{\sqrt{5}}$.
Dimostro il lemma per induzione... per n=1 è ovvio.
Passo base: n=1... ovvio dato che $F_6=8$.
Passo induttivo: Chiamo $x=3\cdot 2^n$.
Vale $\displaystyle F_{3\cdot 2^{n+1}}=F_{2x}=\frac{b^{2x}-c^{2x}}{\sqrt{5}}=F_{x}(b^x+c^x)$. L'uguaglianza perciò vale anche tra le valutazione 2-adiche di LHS e RHS, quindi applicando l'ipotesi induttiva ottengo:
$\upsilon_2\left(F_{3\cdot 2^{n+1}}\right)=n+2+\upsilon_2(b^x+c^x)$
Quindi resta da dimostrare che $2||b^x+c^x$. Sia $y_0=2,\ y_1=1,\ y_{n+2}=y_{n+1}+y_n$. Vale per induzione $y_k=b^k+c^k$. Questa sequenza ricorsiva modulo 4 assume i valori: $2,1,3,0,3,3$. Quindi dato che $6|3\cdot 2^n$ ottengo $y_x\equiv 2\pmod 4$ che è la tesi.

Lemma dell'Emilia Dato $n\ge 1$ intero vale $\displaystyle \upsilon_2\left(F_{3\cdot 2^n-1}-1\right)=\upsilon_2\left(F_{3\cdot 2^n+1}-1\right)=n+1$
Considero $F_i$ $\pmod 4$ allora la sequenza è completamente periodica è ha come valori $0,1,1,2,3,1$ da cui ottengo con brillante intuito che
$F_{3\cdot 2^n-1}\equiv F_{3\cdot 2^n+1}\equiv 1\pmod 4$. ***
Sia $a=3\cdot 2^n$ allora vale (identità nota) $F_{a-1}F_{a+1}-F_{a}^2=(-1)^a=1$.
Sfrutto ora il lemma di Cencio:
$(F_{a-1}-1)(F_{a-1}+1)\equiv F_{a-1}^2-1\equiv F_{a-1}\left(F_a+F_{a-1}\right)-1\equiv F_{a-1}F_{a+1}-F_{a}^2-1\equiv 0\pmod{2^{n+2}}$.
Ma dalla *** ottengo $2||F_{a-1}+1$ quindi $2^{n+1}|F_{a-1}-1$
Ora invece analizzo $\pmod{2^{n+3}}$ e salto passaggi tanto è come prima:
$(F_{a-1}-1)(F_{a-1}+1)+2^{n+2} \equiv (F_{a-1}-1)(F_{a-1}+1)+F_{a-1}F_a\equiv F_{a-1}\left(F_a+F_{a-1}\right)-1\equiv 0\pmod{2^{n+3}}$.
E quindi $2^{n+2}\not| F_{a-1}-1$. Quindi vale $\upsilon_2\left(F_{3\cdot 2^n-1}-1\right)=n+1$, similmente per $F_{3\cdot 2^n+1}$ dato che $F_{3\cdot 2^n+1}=F_{3\cdot 2^n}+F_{3\cdot 2^n-1}\equiv F_{3\cdot 2^n-1}\pmod{2^{n+2}}$

Lemma delle domande consuete Siano $x_0,x_1$ interi non entrambi pari. Definisco $x_{i+2}=x_{i+1}+x_i$. Allora dato $n\ge 1$ il minor $k>0$ tale che $(x_0,x_1)\equiv (x_k,x_{k+1})\pmod{2^{n+1}}$ è $3\cdot 2^n$
Vale facilmente per induzione: $x_n=x_0F_{n-1}+x_1F_n$ quindi applicando il lemma di cencio e dell'Emilia vale:
$x_{3\cdot 2^n}=x_0F_{3\cdot 2^n-1}+x_1F_{3\cdot 2^n}\equiv x_0\pmod{2^{n+1}}$
$x_{3\cdot 2^n+1}=x_0F_{3\cdot 2^n}+x_1F_{3\cdot 2^n+1}\equiv x_1\pmod{2^{n+1}}$
Quindi vale per $k=3\cdot 2^n$: $(x_0,x_1)\equiv(x_k,x_{k+1})\pmod{2^{n+1}}$
Se valesse per un $k$ minore, dato che la roba è periodica modulo $2^{n+1}$, l'altro $k$ dovrebbe comunque dividere $3\cdot 2^n$ ma allora divide anche o $2^n$ o $3\cdot 2^{n-1}$ e quindi dovrebbe valere la congruenza tra le coppie ordinate anche per uno di questi 2 moduli.
Assumo per assurdo valga ponendo $k=2^n$ ma allora ho un facile assurdo dato che in $\{x_0,x_1,x_k,x_{k+1}\}$ c'è almeno un pari (modulo 2 il periodo è 3 e lì ci stanno tutti i rappresentanti modulo 3) ma $0\not\equiv 2^n\pmod 3$ e $1\not\equiv 2^{n}+1\pmod{3}$ quindi vale $(x_0,x_1)\not\equiv (x_k,x_{k+1})\pmod 2$ ma se non vale modulo 2 tantomeno varrà modulo una potenza di 2.
Assumo per assurdo valga ponendo $k=3\cdot 2^{n-1}$. Assumo WLOG $x_0$ dispari (se fosse pari allora $x_1$ sarebbe dispari e i ragionamenti si potrebbero riapplicare praticamente allo stesso modo).
Allora dovrebbe valere (sempre usando il lemma di cencio e dell'emilia):
$x_0\equiv x_k=x_0F_{k-1}+x_1F_k\equiv x_0F_{k-1}\pmod{2^{n+1}}\Rightarrow 2^{n+1}|F_{k-1}-1$ che però contraddice il lemma dell'Emilia.
Quindi ho dimostrato anche il lemma delle domande consuete... yuppie

E ora arrivo finalmente al problema
Prendo la griglia $2^{n}$x$2^{n}$ e collego tutte le coppie di caselle della forma $(i,j)$ e $(j,i+j)$ formando così un grafo. Questo grafo avrà varie parti connesse... il problema mi dice che in ogni componente connessa può esserci un solo colore. Quindi il massimo numero di colori realizzabili è ovviamente il numero delle parti connesse. Inoltre è facile notare che ogni componente connessa è un ciclo (se siete arrivati fino a qui capendo tutti i lemmi questo sarà ovvissimo). Inoltre se in una parte connessa ho una casella (i,j) tale che $2^m||(i,j)$ allora tutte le caselle in quella componente connessa rispettano questo. Quindi associo ad ogni componente la sua valutazione 2-adica.
Prendo una componente connessa con valutazione $k<n-1$, allora prendo un suo elemento $i,j$, e pongo $x_0=i\cdot2^{-k},x_1=j\cdot2^{-k}$. Così facendo al posto di dover analizzare la sequenza modulo $2^{n}$ la devo analizzare modulo $2^{n-k}$. Sono rispettate le ipotesi del lemma delle domande consuete quindi lo applico e trovo che la componente connessa con valutazione $k$ contiene esattamente $3\cdot 2^{n-k-1}$ vertici. Inoltre le caselle con valutazione $k$ sono quelle con valutazione almeno $k$ meno quello con valutazione almeno $k+1$ quindi (facendo i conti) : $3\cdot 2^{2(n-k-1)}$. Quindi facendo la divisione ottengo che le componenti connesse con valutazione $k$ sono: $2^{n-k-1}$
Inoltre c'è un'unica componente con valutazione $n$ e una sola con valutazione $n-1$ (si vede a mano).
Quindi il totale delle componenti connesse e quindi il massimo dei colori utilizzabili è: $\displaystyle 1+1+\sum_{k=0}^{n-2}2^{n-1-k}=2+2^n-2=2^n$ che è la tesi del problema... alleluia

p.s. piccola nota... il problema in realtà chiede di dimostrare che il periodo di Fibonacci modulo $2^{n+1}$ è $3\cdot 2^n$ (cioè lemma di cencio e dell'Emilia)... fatto questo poi il problema è in discesa

[53thebest]

Bravo!!!! (devi essere contento di aver appena risolto l'N6 della Shortlist dell'anno scorso )
La mia soluzione e' praticamente identica alla tua solo che dimostro i lemmi "del ciencio e dell'Emilia" + facilmente ( )con queste:
$$
F_{2n}=F_{n} \cdot (F_{n-1}+F{n+1})
$$
e
$$
F_{2n-1}=F_{n}^2+F_{n-1}^2
$$
(che puoi facilmente trovare su wikipedia, e solo li' visto che non credo esista persona al mondo che se le ricordi ), comunque esiste un modo intelligente di ricavarsi tutte queste formule che la notazione matriciale di fibonacci (e che non scrivero' visto che non so fare matrici in Latex e non ho voglia di cercare nella guida , comunque si trova anche quella su wiki (pero'forse nella pagina in inglese))

[dario2994]

Uhuh... soddisfattissimo
A dir la verità anche io avevo cercato formule per esprimere $F_{2n}$ ma evidentemente non con abbastanza insistenza