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

Solución. Tenemos que multiplicar $1+x+x^2$ por sí mismo $n$ veces, luego cada sumando del resultado viene de elegir un sumando en cada uno de los paréntesis en \[(1+x+x^2)(1+x+x^2)\stackrel{n}{\cdots}(1+x+x^2),\] es decir, tenemos que hacer $n$ elecciones entre los monomios $1=x^0$, $x=x^1$ y $x^2$. Como en el producto se suman los grados de los monomios, habrá tantos términos de grado $k$ como soluciones tenga la ecuación \[t_1+t_2+\ldots+t_n=k,\] con $t_i\in\{0,1,2\}$ para todo $i\in\{1,\ldots,n\}$. En otras palabras, si llamamos $s_k$ al número de soluciones, $s_k$ será precisamente el coeficiente de $x^k$ al desarrollar $(1+x+x^2)^n$. Algunas observaciones iniciales son las siguientes:

• Se cumple que $s_0=1$ ya que la única solución de $t_1+t_2+\ldots+t_n=0$ es $t_1=t_2=\ldots=t_n=0$. De la misma forma, $s_{2n}=1$ ya que la única solución de $t_1+t_2+\ldots+t_n=2n$ es $t_1=t_2=\ldots=t_n=n$.
• Se cumple que $s_n$ es impar. Para probarlo, observamos que si tenemos una solución de $t_1+t_2+\ldots+t_n=0$, entonces podemos asociarle otra intercambiando las variables que son $0$ por $2$ y viceversa mientras dejamos las que son $1$ sin cambiar. Por tanto, todas las soluciones tienen su pareja excepto una: la solución $t_1=t_2=\ldots=t_n=1$.
• Se cumple que $s_{2n-k}=s_k$. Esto se demuestra teniendo en cuenta que una solución de $t_1+t_2+\ldots+t_n=k$ se transforma en una solución de $t_1+t_2+\ldots+t_n=2n-k$ como en el punto anterior cambiando los ceros por doses y los doses por ceros.

Una vez visto esto, ya sabemos que hay siempre al menos tres términos con coeficiente impar. Vamos a probar ahora que si $n=2^m$, entonces estos tres son los únicos. Para ello usaremos inducción sobre $m$; si $m=1$ o $m=2$ el resultado está claro. Para $m\gt 2$, tenemos que cada solución de $t_1+t_2+\ldots+t_n=k$ con $0\lt k\lt n$ está emparejada con otra solución: la que resulta de cambiar los $2^{m-1}$ primeras variables en bloque por las $2^{m-1}$ últimas variables. Las únicas soluciones que están emparejadas con sigo mismas son las que tienen las primeras $n$ variables iguales que las $n$ últimas (es decir, $t_i=t_{i+\frac{n}{2}}$ para todo $i\in\{1,\ldots,\frac{n}{2}$), pero entonces $k$ tiene que ser par y los primeros $2^{m-1}$ términos son una solución de la ecuación $t_1+t_2+\ldots+t_{n/2}=\frac{k}{2}$. La hipótesis de inducción nos dice que el número de soluciones es par, luego tenemos el resultado par que queríamos probar.

Queda por ver que si $n$ no es una potencia de $2$, entonces hay algún coeficiente impar para terminar con todos los casos. Expresemos en este caso $n=a2^m$ para cierto entero impar $a\geq 3$ y veamos que la ecuación $t_1+t_2+\ldots+t_n=k$ tiene un número impar de soluciones para $k=2^m$. Para ello, descomponemos las variables $t_1,\ldots,t_n$ en $a$ grupos de $2^m$ variables consecutivas. Para cada solución, podemos rotar cíclicamente las variables en todos los grupos simultáneamente. Mediante este proceso, podemos agrupar las soluciones en grupos de $2^h$ soluciones con $h\leq m$, excepto si la solución es constante en cada grupo de variables. Esto sólo puede ocurrir si todas las variables son $1$ en uno de los grupos y $0$ en los otros grupos. Como hay un número impar de grupos, esto último nos da un número impar de soluciones y hemos probado lo que queríamos.

En resumen, la solución al problema son las potencias de $2$.

Nota. La solución está inspirada por la versión combinatoria del binomio de Newton.