FOFO 12 Años - Problema 5

[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?

[Joacoini]

Aquí publicaremos la solución oficial.

[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]

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$.