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

Solución. Observemos que si $n$ no es una potencia de $3$, entonces $n=ab$, siendo $a\gt 1$ un número que no es múltiplo de $3$. Tomando $x=2^b$, podemos expresar el número del enunciado como $4^n+2^n+1=x^{2a}+x^a+1$. El resto de la solución se centrará en ver que si $a$ no es múltiplo de $3$, entonces $x^{2a}+x^a+1$ es divisible (como polinomio) entre $x^2+x+1$. Esto se debe a que tenemos que $1\lt x^2+x+1\lt x^{2a}+x^a+1$, luego habremos encontrado un factor no trivial de $4^n+2^n+1=x^{2a}+x^a+1$ y, por tanto, este número será compuesto.

Hay varias formas de ver que $x^2+x+1$ es un factor de $x^{2a}+x^a+1$:

1. La primera es haciendo la división euclídea con un poco de pericia.
2. La segunda es encontrando otro polinomio $p(x)$ tal que $x^{2a}+x^a+1=(x^2+x+1)\cdot p(x)$, lo cual no es muy difícil después de probar unos cuantos casos.
3. La tercera forma es observar que $x^2+x+1$ tiene por raíces complejas $w_1=\frac{-1}{2}+i\frac{\sqrt{3}}{2}$ y $w_2=\frac{-1}{2}-i\frac{\sqrt{3}}{2}$, que cumplen las relaciones $w_1^2=w_2$, $w_2^2=w_1$ y $w_1^3=w_2^3=1$ (son raíces cúbicas de la unidad). Por tanto, \[w_i^{2a}+w_i^a+1=1+w_1+w_2=1-\frac{1}{2}+i\frac{\sqrt{3}}{2}-\frac{1}{2}-i\frac{\sqrt{3}}{2}=0,\] ya que $w_i^{2a}$ y $w_i^a$ son los números $w_1$ y $w_2$ en algún orden (y aquí estamos usando que $a$ no es múltiplo de $3$). Así hemos probado que $w_1$ y $w_2$ son también raíces de $x^{2a}+x^a+1$, con lo que $x^2+x+1$ divide a este polinomio y hemos terminado.

Solución. Dados $m$ y $n$, llamemos $F(m,n)$ al número del enunciado y procedamos por inducción sobre $n$. Para $n=0$ y cualquier $m\geq 0$ se tiene que $$F(m,0)=\left(\begin{array}{c}2m\\m\end{array}\right),$$ que un número combinatorio y, por tanto, entero (hemos hecho uso de que $0!=1$). Supongamos ahora que $F(m,n)$ es entero para todo $m\geq 0$ y probemos que $F(m,n+1)$ también es entero para todo $m\geq 0$. Para probar esto, observemos que, para cualesquiera $m,n\geq 0$, tenemos que \begin{eqnarray*} F(m,n+1)+F(m+1,n)&=&\frac{(2m)!(2n+2)!}{m!(n+1)!(m+n+1)!}+\frac{(2m+2)!(2n)!}{(m+1)!\,n!(m+n+1)!}\\ &=&\frac{(2m)!(2n)!}{m!\,n!(m+n)!}\left(\frac{(2n+2)(2n+1)}{(n+1)(m+n+1)}+\frac{(2m+2)(2m+1)}{(m+1)(m+n+1)}\right)\\ &=&\frac{(2m)!(2n)!}{m!\,n!(m+n)!}\cdot\frac{2(2n+1)+2(2m+1)}{(m+n+1)}=4F(m,n),\\ \end{eqnarray*} donde hemos sacado factor común todos los factoriales posibles y después operado. En particular, se tiene que $F(m,n+1)=4F(m,n)-F(m+1,n)$ es entero ya que $F(m,n)$ y $F(m+1,n)$ son enteros por hipótesis de inducción. Esto concluye la demostración.

Nota. Puede pensarse que esta forma de demostrar que el número es entero es muy rebuscada, pero la idea es muy similar a la demostración de que los números combinatorios son enteros (concretamente, se prueba que un número combinatorio es la suma de los dos que están por encima de él en el triángulo de Tartaglia).

Solución. Tomando congruencias módulo $3$, observamos que $3^n\equiv 0\ (\mathrm{mod}\ 3)$ para todo $n$ mientras que $2^n\equiv 2\ (\mathrm{mod}\ 3)$ para $n$ impar y $2^n\equiv 1\ (\mathrm{mod}\ 3)$ para $n$ par. Deducimos así que $2^n+3^n\equiv 2\ (\mathrm{mod}\ 3)$ para $n$ impar. Ahora bien, todos los cuadrados son congruentes con $0$ ó $1$ módulo $3$, lo que nos lleva a que $2^n+3^n$ no puede ser un cuadrado.

Solución. Vamos a proceder por inducción sobre $n$. Para $n=1$, tenemos que las posibles sumas son $0\cdot 0=0\cdot1=1\cdot 0=0$ y $1\cdot 1=1$, con lo que $I(1)=1$, $P(1)=3$ y la fórmula del enunciado se cumple.

Supongamos ahora que la igualdad es cierta para $n$ y veamos qué pasa para una suma de $n+1$ términos. Dicha suma será par cuando la suma de los $n$ primeros productos y el último producto sean ambos pares o ambos impares. Como el último producto tiene tres formas de ser par ($0\cdot 0=0\cdot1=1\cdot 0=0$) y una de ser impar $1\cdot 1=1$, llegamos a que $$P(n+1)=I(n)+3P(n).$$ Análogamente, la suma de los $n+1$ productos será impar cuando la suma de los $n$ primeros y el útlimo tengan distinta paridad, lo que nos lleva en este caso a la identidad $$I(n+1)=3I(n)+P(n).$$ Dividiendo ambas igualdades y usando la hipótesis de inducción tenemos que $$\frac{P(n+1)}{I(n+1)}=\frac{I(n)+3P(n)}{3I(n)+P(n)}=\frac{1+3\frac{P(n)}{I(n)}}{3+\frac{P(n)}{I(n)}}=\frac{1+3\frac{2^n+1}{2^n-1}}{3+\frac{2^n+1}{2^n-1}}=\frac{2^{n+1}+1}{2^{n+1}-1}{,}$$ que es la fórmula que se pretendía demostrar para $n+1$.

Nota. De hecho, a partir de aquí se puede calcular fácilmente el valor exacto de $P(n)$ e $I(n)$, dado que se sabe que $P(n)+I(n)=2^{2n}$, el número total de $2n$-uplas de ceros y unos. Concretamente se llega a que \begin{eqnarray} P(n)&=&2^{2n-1}+2^{n-1}{,}\\ I(n)&=&2^{2n-1}-2^{n-1}{.} \end{eqnarray}

Solución. En primer lugar, expresamos $$P(x,y)=2x^2-6xy+5y^2=(x-2y)^2+(x-y)^2{.}$$ De aquí deducimos que todos los valores de $P$ son suma de dos cuadrados. No obstante, cualquier suma de dos cuadrados $u^2+v^2$ es un valor de $P$, sin más que tomar $x=-u+2v$ e $y=-u+v$ en la expresión de arriaba. Esto nos dice que los valores de $P$ son exactamente los números enteros que se expresan como suma de dos cuadrados.

Por inspección directa, los números menores o iguales que 100 que son suma de dos cuadrados son: 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100. Estos hacen un total de 43 valores de $P$ entre 1 y 100, lo que responde al apartado (a).

Para responder al apartado (b), veamos ahora que el producto de dos números que se expresan como suma de dos cuadrados vuelve a ser suma de dos cuadrados, pero esto es consecuencia de la siguiente identidad, válida para cualesquiera números $a$, $b$, $c$ y $d$ no necesariamente enteros: $$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2{.}$$