FOFO de Pascua - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
lucasdeamorin

FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 96
Registrado: Dom 22 Dic, 2013 9:17 pm
Medallas: 9
Nivel: Otro

FOFO de Pascua - Problema 5

Mensaje sin leer por lucasdeamorin »

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$.
Si X tiende a [math], [math] se seca.
lucasdeamorin

FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 96
Registrado: Dom 22 Dic, 2013 9:17 pm
Medallas: 9
Nivel: Otro

Re: FOFO de Pascua - Problema 5

Mensaje sin leer por lucasdeamorin »

Aquí se publicará la solución oficial
Si X tiende a [math], [math] se seca.
FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 41
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 8
Nivel: 3
Ubicación: Corrientes

Re: FOFO de Pascua - Problema 5

Mensaje sin leer por FabriATK »

Spoiler: mostrar
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"):

Le colocamos una pieza individual verde:
Spoiler: mostrar
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)$
Le colocamos una pieza individual roja:
Spoiler: mostrar
De manera análoga al caso anterior, nos quedan $S(2022)\times S(2022)$ formas de llenar el tablero
Le colocamos una pieza negra que ocupa $(C_{2023}, C_{2024})$
Spoiler: mostrar
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})$
Spoiler: mostrar
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.
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 1054
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 19
Nivel: Exolímpico
Ubicación: Santa Fe

Re: FOFO de Pascua - Problema 5

Mensaje sin leer por Fran5 »

Solución +18
Spoiler: mostrar
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}$$

Como $A_1 = 2$ y $A_2 = 5$, tenemos que $$ c_1 \left( 1 + \sqrt{2} \right) + c_2 \left( 1 - \sqrt{2} \right) = 2$$ $$ c_1 \left( 1 + \sqrt{2} \right)^2 + c_2 \left( 1 - \sqrt{2} \right)^2 = 5$$

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 :D
Spoiler: mostrar
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 //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 1925
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO de Pascua - Problema 5

Mensaje sin leer por Gianni De Rico »

Solución (+18)++
Spoiler: mostrar
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 pongo 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.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Responder