Se tienen fichas de $1\times 1$ rojas y verdes, y fichas de $1\times 2$ negras. Demostrar que la cantidad de formas de completar un tablero de $1\times 2022$ divide a la cantidad de formas de completar un tablero de $1\times 4045$.
Sea $S(X)$, la cantidad de maneras de llenar un tablero de $1 \times X$ con las fichas descriptas en el enunciado.
$4045 = 2\times 2022 + 1$
Enumeremos de izquierda a derecha las casillas del tablero, desde $C_1$ hasta $C_{4045}$
Ahora, dividimos las maneras de completar todo el tablero de $1 \times 4045$ en $4$, según la forma en la que completamos la casilla $C_{2023}$("la casilla del medio"):
De esta forma, el tablero se divide en dos subtableros de $2022$ casillas cada uno que no se relacionan. Es decir que la cantidad de maneras de completar el tablero en este caso es $S(2022)\times S(2022)$
Ahora, el tablero queda dividido en dos subtableros, uno de $2022$ casilla y el otro de $2021$. Y la cantidad de maneras de llenarlo será: $S(2022) \times S(2021)$
Le colocamos una pieza negra que ocupa $(C_{2022}, C_{2023})$
Similar al caso anterior, nos quedan $S(2022) \times S(2021)$ maneras de llenarlo.
Y como distribuimos a todas las formas de llenar el tablero en esa cuatro opciones, $S(4045)$ será igual a la suma de esas cantidades. $S(4045) = 2\times S(2022)^2 + 2\times S(2022)\times S(2021) = 2\times S(2022)\times (S(2022) + S(2021))$ que es múltiplo de $S(2022)$ y estamos.
Sea $A_n$ la cantidad de formas de rellenar el tablero de $1 \times n$.
Claramente, podemos poner una ficha roja o verde en la primer casilla, quedando un tablero de $1 \times (n-1)$ ó una ficha negra quedando un tablero de $1 \times (n-2)$. Luego tenemos $$A_n =2A_{n-1} + A_{n-2}$$
Como es una relación de recurrencia, queremos encontrar entonces constantes $c_1,c_2, p,q$ tales que $$A_n = c_1 p^n + c_2 q^n$$
Entonces $p,q$ son las raíces del polinomio $x^2- 2x-1$ de donde $$p,q = \dfrac{2 \pm \sqrt {2^2 - 4\cdot(-1)}}{2} = 1 \pm \sqrt{2}$$
Este es un sistema de 2x2 que podemos resolver con nuestra herramienta favorita, de donde $$c_1 = \frac{1}{2} + \frac{1}{2 \sqrt{2}} = \frac{1 + \sqrt{2}}{2 \sqrt{2}}$$ $$ c_2 = - \frac{1- \sqrt{2}}{2 \sqrt{2}}$$
Finalmente, basta ver que $$\frac{A_{2n+1}}{A_n} = \frac{ \frac{1+ \sqrt{2}}{2 \sqrt{2}} (1+ \sqrt{2})^{2n+1} - \frac{1- \sqrt{2}}{2 \sqrt{2}} (1- \sqrt{2})^{2n+1} } { \frac{1+ \sqrt{2}}{2 \sqrt{2}}(1+ \sqrt{2})^{n} - \frac{1- \sqrt{2}}{2 \sqrt{2}} (1- \sqrt{2})^{n} } = \frac{ (1+ \sqrt{2})^{2n+2} - (1- \sqrt{2})^{2n+2} } { (1+ \sqrt{2})^{n+1} - (1- \sqrt{2})^{n+1} }$$ es un número entero
Como $2n+2$ es par, tenemos $$\frac{A_{2n+1}}{A_n} = (1+ \sqrt{2})^{n+1} +(1- \sqrt{2})^{n+1}$$
Finalmente del finalmente, es conocido que todo numero de la forma $(a + \sqrt{b})^n + (a - \sqrt{b})^n$ es entero, de donde el cociente $\frac{A_{2n+1}}{A_n}$ es entero
desarrollar el binomio.. los sumandos con exponente impar en $\sqrt{b}$ se cancelan mutuamente, mientras que los sumandos con exponente par en $\sqrt{b}$ nos dan un número entero.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Podemos pensar el problema como llenar un tablero de $2\times 2022$ con dominós horizontales de un color y dominós verticales de $2$ colores.
Sea $f(n,k)$ la cantidad de formas de llenar un tablero de $2\times n$ con dominós horizontales de un color y dominós verticales de $k$ colores, vamos a demostrar que $f(n,k)\mid f(2n+1,k)$. El problema es el caso particular $n=2022$ y $k=2$. Se sabe (se puede probar con inducción) que con $k=1$ nos da $f(n,k)=F_{n+1}$, Fibonacci, así que acá también tiene que aparecer Fibonacci.
Notemos que $f(1,k)=k$, $f(2,k)=k^2+1$ y $f(n,k)=kf(n-1,k)+f(n-2,k)$ para $n\geq 3$, dependiendo de si en la primera columna ponemos un dominó vertical o dos dominós horizontales.
Por la recurrencia de los Polinomios de Fibonacci tenemos que $f(n,k)=F_{n+1}(k)$ para todos $n,k\in \mathbb{N}$. Entonces $f(2n+1,k)=F_{2(n+1)}(k)$, y usando la identidad $F_{2m}(x)=F_m(x)L_m(x)$, como todos son polinomios con coeficientes enteros, se tiene que $F_{n+1}(k)\mid F_{2(n+1)}(k)$, es decir, $f(n,k)\mid f(2n+1,k)$, como queríamos.