Ibero 2017 - P3

Ibero 2017 - P3

UNREAD_POSTpor Violeta » Mar 19 Sep, 2017 2:45 pm

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.
Para todo $k$, existen $k$ primos en sucesión aritmética.
Avatar de Usuario
Violeta
 
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Ubicación: Puerto Rico
Medals: 1
OFO - Mención

Re: Ibero 2017 - P3

UNREAD_POSTpor jujumas » Jue 21 Sep, 2017 12:43 pm

Solución:
Spoiler: Mostrar
Notemos que podemos ubicar los números en un triangulo de $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 $g(n)$ la minima cantidad de ceros que puede haber en los pisos con $n-2$, $n-1$ y $n$ números, vamos a demostrar que $g(n)\geq n-1$ para todo $n$. Esto lo veremos con inducción fuerte.

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

Supongamos ahora que para todo $n \leq k$, $g(n)\geq n-1$. Vamos a demostrar que $g(k+1)\geq k$. Para esto, notemos que la estructura con los pisos de longitud $k+1$, $k$ y $k-1$ se puede dividir en dos estructuras de longitudes de pisos $k-2$, $k-3$ y $k-4$ y en otra de longitud $3$, $2$ y $1$ a su derecha. Sumando estos mínimos, obtenemos que $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 $k+1 \geq 7$, esta estructura también se puede dividir en dos de longitudes de pisos $k-3$, $k-4$ y $k-5$ y en otra de longitud $4$, $3$ y $2$ a su derecha, con lo que la única forma de que $g(k+1)=k-1$ seria que hubiese un trapecio con $5$ números que apunte hacia abajo con solo unos, pero esto implica que dos unos suman otro uno, lo que es imposible. Luego, $g(k+1)\geq k$ para todo $k$.

Usando estas desigualdades, obtenemos que hay como mínimo $\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 $\frac{2017 \times 2018 - (2016 \times 673)}{2}$ números impares.

Este máximo se puede obtener (por ejemplo) coloreando el triangulo de $3$ colores de forma que no haya dos casillas que se toquen que sean del mismo color, y ubicando un $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.

jujumas
 
Mensajes: 313
Registrado: Dom 26 Oct, 2014 8:30 pm
Medals: 5
OFO - Mención OFO - Medalla de Plata FOFO 6 años - Medalla Especial OFO - Oro perfecto
FOFO Pascua 2017 - Medalla
Nivel: 2


Volver a Combinatoria

¿Quién está conectado?

Usuarios navegando por este Foro: Bing [Bot] y 1 invitado