Olimpiadas de Matemáticas
Página de preparación y problemas

• El número de formas de colocar los cambios de color es el número de elegir $m$ de los $n$ lados del polígono, lo que nos da $\binom{n}{m}$ posibilidades.
• Para el número de formas de asignar los colores no importa dónde se produzcan los cambios. Hay que elegir $m+1$ colores de forma que dos consecutivos sean distintos y el primero y el último sean iguales. Pongamos que coloreamos de esta forma los números del $1$ al $m+1$ y llamemos $x_m$ al número de formas de hacerlo. Si pensamos en los números del $1$ al $m-1$, hay dos posibilidades: que el $m-1$ y el $1$ tengan el mismo color (en cuyo caso hay dos formas de completar hasta el $m+1$) o que el color sea distinto (en cuyo caso hay dos formas de completar). Esto último equivale a poder colorear del $1$ al $m$ con $m$ del mismo color que el $1$, con lo que se obtiene la recurrencia $x_m=2x_{m-2}+x_{m-1}$.

  Esta recurrencia tiene polinomio característico $p(x)=x^2-x-2=(x+1)(x+2)$, luego la solución admite una fórmula del tipo $x_m= a2^m+b(-1)^m$ para ciertas constantes $a$ y $b$. Es fácil ver que $x_2=x_3=6$, luego se debe cumplir que $x_2=4a+b=6$ y $x_3=8a-b=6$. Esto nos lleva a que $a=1$ y $b=2$, luego se tiene que $x_m=2^m+2(-1)^m$.

En conclusión, la respuesta al problema es \[\binom{n}{m}(2^m+2(-1)^m).\]