Ibero 2017 - P3

[Violeta]

Consideramos las configuraciones de números enteros$$\begin{array}{ccccc}
a_{1,1} & & & & \\
a_{2,1} & a_{2,2} & & & \\
a_{3,1} & a_{3,2} & a_{3,3} & & \\
\vdots & \vdots & \vdots & \ddots & \\
a_{2017,1} & a_{2017,2} & a_{2017,3} & \cdots & a_{2017,2017}
\end{array}$$con $a_{i,~j}=a_{i+1,~j}+a_{i+1,~j+1}$ para todos los $i,j$ tales que $1\leq j\leq i\leq 2016$.
Determinar la máxima cantidad de enteros impares que puede contener una tal configuración.

[jujumas]

Solución:

Spoiler: mostrar

Notemos que podemos ubicar los números en un triangulo de [math]2017 pisos en donde en cada piso hay un numero mas que en el anterior, y la suma de dos números adyacentes del mismo piso es igual al numero sobre ellos dos en el piso siguiente. Ademas, como solo nos interesa la paridad de los números, podemos llenar el triangulo de solamente unos y ceros. Lo que queremos hacer es equivalente a ver cual es la mínima cantidad de ceros que puede haber en dicha pirámide.

Sea [math]g(n) la minima cantidad de ceros que puede haber en los pisos con [math]n-2, [math]n-1 y [math]n números, vamos a demostrar que [math]g(n)\geq n-1 para todo [math]n. Esto lo veremos con inducción fuerte.

Vamos a tomar como casos bases [math]n=3, [math]n=4, [math]n=5 y [math]n=6. Para ver estos casos, simplemente vemos todas las formas de llenar con unos y ceros el piso de abajo, que son [math]64 sin contar simetrías, y vemos que la cantidad de ceros nunca es menor a [math]n-1.

Supongamos ahora que para todo [math]n \leq k, [math]g(n)\geq n-1. Vamos a demostrar que [math]g(k+1)\geq k. Para esto, notemos que la estructura con los pisos de longitud [math]k+1, [math]k y [math]k-1 se puede dividir en dos estructuras de longitudes de pisos [math]k-2, [math]k-3 y [math]k-4 y en otra de longitud [math]3, [math]2 y [math]1 a su derecha. Sumando estos mínimos, obtenemos que [math]g(k+1)\geq g(k-2)+g(3)=k-1, con igualdad solo si el triangulo que no esta en ninguna de las dos estructuras contiene solamente unos.
Ademas, como [math]k+1 \geq 7, esta estructura también se puede dividir en dos de longitudes de pisos [math]k-3, [math]k-4 y [math]k-5 y en otra de longitud [math]4, [math]3 y [math]2 a su derecha, con lo que la única forma de que [math]g(k+1)=k-1 seria que hubiese un trapecio con [math]5 números que apunte hacia abajo con solo unos, pero esto implica que dos unos suman otro uno, lo que es imposible. Luego, [math]g(k+1)\geq k para todo [math]k.

Usando estas desigualdades, obtenemos que hay como mínimo [math]\sum_{i=1}^{672} g(3i+1) \geq \sum_{i=1}^{672} 3i = 3 \sum_{i=1}^{672} i = \frac{3 \times 672 \times 673}{2} números pares, y que hay un máximo de [math]\frac{2017 \times 2018 - (2016 \times 673)}{2} números impares.

Este máximo se puede obtener (por ejemplo) coloreando el triangulo de [math]3 colores de forma que no haya dos casillas que se toquen que sean del mismo color, y ubicando un [math]0 en todas las casillas con el color que tenga el cuadrado derecho del segundo piso (contando desde arriba), lo que demuestra que este numero es el máximo.