FOFO 12 Años - Problema 5

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 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: 413
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 12
Nivel: Exolímpico
Ubicación: Ciudad Gotica

FOFO 12 Años - Problema 5

Mensaje sin leer por Joacoini »

Joacoini compró una casita con forma de $n$-ágono regular para su perra OMA. Joacoini, que es una persona muy apasionada por la moda, quiere decorarla pintando cada lado de rojo, azul o verde. Joacoini dice que una forma de pintar la casita es divertida si no hay dos lados adyacentes pintados del mismo color. ¿Cuál es la cantidad de formas divertidas de pintar la casita?
NO HAY ANÁLISIS.
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 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: 413
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 12
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: FOFO 12 Años - Problema 5

Mensaje sin leer por Joacoini »

Aquí publicaremos la solución oficial.
NO HAY ANÁLISIS.
El gran Filipikachu;

OFO - Medalla de Bronce-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: 23
Registrado: Dom 13 Dic, 2020 12:33 pm
Medallas: 4
Nivel: 2

Re: FOFO 12 Años - Problema 5

Mensaje sin leer por El gran Filipikachu; »

Spoiler: mostrar
Sean $a_1$ hasta $a_n$ los $n$ lados del polígono en sentido horario. Sin pérdida de generalidad digamos que la puerta de la casa de OMA está en $a_1$.
$A$ es azul, $R$ es rojo y $V$ es verde.
Definamos $F(n)$ como la cantidad de formas divertidas de pintar la casita.

$n=3$
WLOG $a_1$ es $A$. Ahora quedan dos casos válidos que funcionan ($a_2$ de color $R$, $a_3$ de color $V$ y viceversa). Multiplicando por $3$ (porque $a_1$ puede ser $A$, $R$ o $V$) tenemos en total $6$ casos.
Entonces $F(3)=6$

$n=4$
WLOG $a_1$ es $A$.
Si hay un solo $A$, tenemos dos posibildades ($a_2$ y $a_4$ de color $R$ con $a_3$ de color $V$ y viceversa).
Si hay dos $A$, la segunda será $a_3$. Para $a_2$ tenemos dos posibilidades y para $a_4$ también. En este caso hay $2\cdot2=4$ en total.
Multiplicando por $3$ tenemos que $F(4)=18$

Para $n \geq 5$ vamos a obtener $F(n)$ a partir de $F(n-1)$ y $F(n-2)$

Tenemos pintadas las $n$ paredes
Vamos a separar en dos casos: cuando $a_1$ y $a_{n-1}$ son de distinto color y cuando $a_1$ es del color de $a_{n-1}$

Caso $1$: $a_1$ y $a_{n-1}$ son de distinto color.
Al tener $a_1$ y $a_{n-1}$ distinto color, es claro que $a_n$ debe ser del tercer color. Como todas son de distinto color, podemos eliminar $a_n$ y obtenemos una coloración que pertenece a $F(n-1)$.
Veamos también que dada una coloración de $F(n-1)$, si agregamos el tercer color faltante entre $a_1$ y $a_{n-1}$ obtenemos una coloración que pertenece a $F(n)$.
Notemos que el orden de realizar estas dos operaciones mantiene todo igual, por lo que para cada coloración de $F(n-1)$ hay exactamente una coloración de $F(n)$ y para cada coloración de este tipo de $F(n)$ hay exactamente una coloración en $F(n-1)$. Por lo tanto tenemos una biyección y en este caso hay $F(n-1)$ coloraciones.

Caso $2$: $a_1$ y $a_{n-1}$ son del mismo color.
En este caso $a_n$ puede ser de dos colores, ya que sus vecinos son del mismo color.
Veamos que si eliminamos $a_n$ y $a_{n-1}$ obtenemos una coloración válida que pertenece a $F(n-2)$. También, dada una coloración de $F(n-2)$ podemos agregar $a_{n-1}$ del mismo color que $a_1$ y $a_n$ de uno de los dos colores que no usamos.
Notemos que realizando estas dos operaciones estamos mandando dos coloraciones de $F(n)$ a una misma coloración en $F(n-2)$ y para cada coloración de $F(n-2)$ tenemos dos coloraciones en $F(n)$. Por lo tanto hay una biyección que agrupa dos coloraciones de $F(n)$ con una coloración de $F(n-2)$. Entonces en este caso hay $2F(n-2)$ coloraciones.

Sumando lo obtenido llegamos a la relación de recurrencia $F(n)=F(n-1)+2F(n-2)$.

Resolviendola tenemos:
$F(n)=F(n-1)+2F(n-2)$
$x^n=x^{n-1}+2x^{n-2}$
$x^2=x+2$
$x^2-x-2=(x+1)(x-2)=0$
Y las raíces son $-1$ y $2$.
Entonces tenemos que $F(n)=a\cdot(-1)^n+b\cdot2^n$
Como $F(3)=6$ y $F(4)=18$ resolvemos
$6=F(3)=a\cdot(-1)^3+b\cdot2^3=-a+8b$
$18=F(4)=a\cdot(-1)^4+b\cdot2^4=a+16b$
Sumando las dos ecuaciones:
$24=24b \Rightarrow b=1 \Rightarrow -a+8=6 \Rightarrow a=2$

Por lo tanto llegamos a que $F(n)=2^n+2\cdot(-1)^n$
Martín Lupin

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022
Mensajes: 31
Registrado: Lun 20 May, 2019 10:26 am
Medallas: 9
Nivel: 2
Ubicación: Mar del Plata

Re: FOFO 12 Años - Problema 5

Mensaje sin leer por Martín Lupin »

Spoiler: mostrar
Vamos a reemplazar los colores por números: el rojo por el $0$, el verde por el $1$ y el azul por el $2$. Tomamos una de las paredes y le ponemos un $0$, y luego vamos a "colorear" el resto en sentido horario. Como no puede haber dos paredes consecutivas con el mismo número, a cada pared le asignamos un número que es $+1$ o $+2$ de la pared anterior (módulo 3). A esta elección de sumar $1$ o $2$ la vamos a representar con el polinomio $x+x^2$. Notemos que luego de expandir el polinomio $P(x)=(x+x^2)^n$, cada término representa cada posibilidad de sumar $1$ o $2$ a cada paso en toda la casa. Además, la suma total de $1$s y $2$s debe ser un múltiplo de $3$ para garantizar que luego de dar la vuelta completa a la casa pintando las paredes, se vuelva al color $0$ de la primera pared. Es decir, que nos interesa la suma de los coeficientes de las potencias de la forma $x^{3k}$ del polinomio $P(x)$. Sea $\omega ^3=1$, $\omega \neq 1$ una raíz cúbica de la unidad. Notemos que $1^k+\omega^k+(\omega^2)^k=0$ si $k\equiv 1, 2 \pmod{3}$, y $1^k+\omega^k+(\omega^2)^k=3$ si $k\equiv 0 \pmod{3}$. Entonces $\frac{P(1)+P(\omega)+P(\omega^2)}{3}=\frac{2^n+(\omega+\omega^2)^n+(\omega^2+\omega^4)^n}{3}=\frac{2^n+(-1)^n+(\omega^2+\omega)^n}{3}=\frac{2^n+2\cdot (-1)^n}{3}$ es la cantidad de posibles coloraciones de la casa. Considerando que la primera pared también podría haber sido pintada de $1$ o $2$, obtenemos que la cantidad total de posibles coloraciones es $2^n+2\cdot (-1)^n$.
7  
Responder