Problema 4 de la Fase Local de la Olimpiada Española de Matemáticas 2021 Se dirige a una edad de: 16-17 años
Al desarrollar (1 + x + x²)n en potencias de x, exactamente tres términos tienen coeficiente impar.
¿Para qué valores de n es esto posible?
Solución:
Los primeros intentos deben ser manipulativos, con objeto de comprender cómo funciona la operación propuesta y establecer una hipótesis sobre qué valores de n tienen esa propiedad.
De esta forma, calcularíamos (1 + x + x²)² = 1 + x + x² + x + x² + x³ + x² + x³ + x⁴ = 1 + 2x + 3x² + 2x³ + x⁴, que tiene exactamente tres términos con un coeficiente impar, por tanto n = 2 cumple las condiciones pedidas (y n = 1 también, claro).
Por otra parte, (x² + x + 1)³ = (x² + x + 1)²·(x² + x + 1) = (1 + 2x + 3x² + 2x³ + x⁴)(x² + x + 1) = 1 + 2x + 3x² + 2x³ + x⁴ + x + 2x² + 3x³ + 2x⁴ + x⁵ + x² + 2x³ + 3x⁴ + 2x⁵ + x⁶ = 1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶, con lo que n = 3 no tiene 3, si no 5 coeficientes impares.
Antes de parar, vamos a probar por última vez, (x² + x + 1)⁴ = (x² + x + 1)³·(x² + x + 1) = (1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶)(x² + x + 1) = 1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶ + x + 3x² + 6x³ + 7x⁴ + 6x⁵ + 3x⁶ + x⁷ + x² + 3x³ + 6x⁴ + 7x⁵ + 6x⁶ + 3x⁷ + x⁸ = 1 + 4x + 10x² + 16x³ + 19x⁴ + 16x⁵ + 10x⁶ + 4x⁷ + x⁸. Evidentemente, n = 4 también cumple la condición.
A partir de aquí, vista la complejidad de continuar, podemos tomar la decisión de cambiar los coeficientes y fijarnos únicamente en la paridad, es decir, poner un 0 cuando sean pares y un 1 cuando sean impares, ya que al multiplicar por un coeficiente par, da un coeficiente par también, y sumarlo a otros coeficientes no cambia su paridad (se comporta exactamente como haría un cero, al multiplicar hace cero, y al sumar no cambia a los demás), mientras que el 1 al multiplicar por otro 1 sigue dando impar. La única diferencia con los números “normales” será que al sumar un 1 y otro 1, situaremos un cero, pues el resultado da un valor par. Este método de trabajo se conoce como trabajar con aritmética de reloj de módulo 2, trabajar con paridad o usar coeficientes módulo 2.
Observamos la ganancia de velocidad de este método:
(1 + x + x²)² = 1 + x + x² + x + x² + x³ + x² + x³ + x⁴ = 1 + x² + x⁴
(1 + x + x²)³ = (1 + x + x²)²(1 + x + x²) = (1 + x² + x⁴)(1 + x + x²) =1 + x + x² + x² + x³ + x⁴ + x⁴ + x⁵ + x⁶ = 1 + x + x³ + x⁵ + x⁶
(1 + x + x²)⁴ = (1 + x + x²)³(1 + x + x²) = (1 + x + x³ + x⁵ + x⁶)(1 + x + x²) =1 + x + x² + x + x² + x³ + x³ + x⁴ + x⁵ + x⁵ + x⁶ + x⁷ + x⁶ + x⁷ + x⁸ = 1 + x⁴ + x⁸
Es más, si situamos en una cuadrícula simulada los coeficientes (en mi caso, usé una hoja en blanco para posicionarlos a mano, pero en casa trabajé con una hoja de cálculo), dejando sólo unos y ceros para representar si ese grado está o no está, la cosa se pone interesante, ya que las sucesivas potencias funcionan como un triángulo de pascal, sólo que de tres en tres, es decir, cada nuevo coeficiente es suma de los tres que tiene arriba, arriba a la derecha, y arriba a la izquierda.
Para que se vea en el dibujo, he dado formato a las celdas para que se muestren los ceros de color blanco sobre fondo rojo y los unos, rojos sobre fondo blanco.
Se puede apreciar que emerge un patrón con una trama muy clara, simétrico, y que nos permite encontrar las claves para acabar la demostración.
Bueno, tras este dibujo, no queda probado aún nada, pero ya podemos hacer una conjetura: los valores de n con exactamente 3 valores impares son las potencias de 2 (n = 1, 2, 4, 8, …)
Veamos cómo demostrarlo.
Hemos visto que en los casos n = 1, 2 y 4 es cierto, sólo hay 3 posiciones con coeficiente impar (1 en nuestra versión simplificada), el término independiente, la potencia de grado n y la de grado 2n.
Supongamos que es cierto para un determinado valor n y veamos que se cumple para 2n (la siguiente potencia de 2).
Puesto que, en nuestra aritmética de pares impares, (1 + x + x²)n = 1 + xn + x2n, por hipótesis de inducción, resulta que (1 + x + x²)2n = ((1 + x + x²)n)² = (1 + x + x²)n(1 + x + x²)n = (1 + xn + x2n)(1 + xn + x2n) = 1 + xn + x2n + xn + x2n + x3n + x2n + x3n + x4n = 1 + x2n + x4n, que es exactamente lo que queremos demostrar (recuerda que cuando sumamos 1 y 1, da cero en nuestra aritmética).
Mucho más difícil es probar que los términos no son potencia de 2 no tienen esta propiedad.
De nuevo mirando el patrón que ha quedado en la construcción anterior, se puede observar unos triángulos en rojo que ocupan todo el espacio entre una potencia de 2 y la siguiente. Eso puede dar una idea de cómo trabajar para probarlo.
Debemos concentrarnos en buscar un cuarto elemento con coeficiente impar (1 en nuestra aritmética), y quedará probado que no hay exactamente 3.
De hecho, es fácil ver que todos los términos tienen un 1 en el término primero (grado cero), en el grado n y en el grado 2n, por simetría.
Puesto que cada término se obtiene sumando tres consecutivos del polinomio anterior, la simetría inicial se mantiene, por lo que el primer término y el último (que son idénticos en todos los casos) tienen coeficiente 1, y el término central, evidentemente, tiene coeficiente impar, pues es suma de un impar (el antiguo central) y dos iguales, el anterior y el siguiente.
De la misma forma que probamos que el término de potencia n = 2k tiene tres coeficientes 1 (impares), es sencillo ver que los términos de potencia n = 2k + 2k + 1 tiene exactamente 5, ya que son los que tiene n = 3 y se puede comprobar de la misma forma que se mantiene cada vez que la potencia n se duplica.
En ese caso, los términos que tienen un coeficiente 1 serán exactamente el de grado 0, el de grado 2k, el de grado 2k + 2k + 1, el de grado 22k + 22k + 2 – 2k y el de grado 22k + 22k + 2. (Para justificarlo debemos de comprobarlo por inducción). Dada la simetría, basta comprobar los dos primeros.
El siguiente paso, es que si tenemos un valor de n que no es exactamente uno de los que es potencia de 2, estará entre una potencia de 2 y la siguiente. Si no es de la forma del caso anterior (2k + 2k + 1), o bien es de la forma 2k + 2k+1 + t. o bien es de la forma 2k + 1 + t, para un valor de t entre 0 y 2k.
Pero cuando uno de los polinomios de la secuencia tiene un hueco de exactamente p “ceros”, el siguiente tiene un hueco de exactamente p – 2 ceros, así que seguro que encontramos un término que vale 1, además de los “seguros” (el de grado 0, el de grado n y el de grado 2n).
¿Por qué sucede esto? Puesto que cada término se calcula sumando tres consecutivos del anterior, es evidente que el primero que coincida con el principio del hueco tendrá un 1, al sumar el anterior al hueco con dos ceros, los siguientes valdrán ceros, hasta el que esté inmediatamente debajo del último, que también tendrá un 1. Evidentemente, la longitud del hueco será exactamente p – 2.
Y, claro, los términos con una n de la forma 2k+1 sabemos que tienen un hueco entre el término cero y el 2k + 1 de exactamente 2k + 1 – 1 ceros, así que si t está entre 0 y 2k, y n es de la forma 2k + 1 + t, podemos predecir que el término de la posición t será 1.
Y los términos con una n de la forma 2k + 2k + 1 hemos visto que tienen un hueco entre el término de grado 2k y el de grado 2k + 2k + 1 de exactamente 2k + 1 – 1 ceros, así que, de la misma forma que antes, si t está entre 0 y 2k, y n es de la forma 2k + 2k + 1 + t, podemos predecir que el término de la posición 2k + t será 1.
Se trata de un problema muy difícil, en el que muy pocas personas llegaron a conjeturar la solución, y muchos menos demostrar la condición definitiva, aunque algunas personas sí que probaron que los valores potencias de 2 tenían tres coeficientes impares por inducción.