Nacional 2009 - P3 N5

Problemas que aparecen en el Archivo de Enunciados.
BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 183
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Nacional 2009 - P3 N5

Mensaje sin leer por BrunZo » Dom 08 Sep, 2019 6:26 pm

Alrededor de una circunferencia están escritos $2009$ enteros, no necesariamente distintos, de modo que si dos números son vecinos su diferencia es $1$ o $2$. Diremos que un número es grande si es mayor que sus dos vecinos, y que es pequeño si es menor que sus dos vecinos. La suma de todos los números grandes es igual a la suma de todos los números pequeños más $1810$. Determinar cuántos números impares puede haber alrededor de la circunferencia.
1  

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1063
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2009 - P3 N5

Mensaje sin leer por Gianni De Rico » Mar 22 Oct, 2019 12:41 pm

Está en la Maratón de Problemas
Matías V5 escribió:
Lun 28 Feb, 2011 2:10 am
Solución al problema 14:
Spoiler: mostrar
Sean $a_1, a_2, ..., a_{2009}$ los números que están (en ese orden) en la circunferencia. Para cada $i$ entre $1$ y $2009$, sea $d_i = a_{i+1} - a_i$ (entendiendo que $a_{2010} = a_1$). Para visualizar mejor podemos pensar que escribimos cada $d_i$ en el arco que une los puntos $a_i$ y $a_{i+1}$.

Por el enunciado, cada $d_i$ puede ser igual a $1$, $2$, $-1$ o $-2$. Sean $a,b,c,d$ la cantidad de $1,2,-1,-2$ que hay entre los $d_i$, respectivamente. Entonces $a+b+c+d = 2009$. $(*)$
Además es claro que la suma de todos los $d_i$ es $0$, por lo tanto $a+2b = c+2d$. $(**)$

Observamos que el $a_i$ es grande si y sólo si $d_{i-1} > 0$ y $d_i < 0$, análogamente el $a_i$ es pequeño si y sólo si $d_{i-1} < 0$ y $d_i > 0$. De esto se deduce que entre dos números grandes siempre hay un número pequeño, y por lo tanto números grandes y pequeños se van alternando en la circunferencia (claro que entre un número grande y un número pequeño puede haber varios números que no son ninguna de las dos cosas). En particular hay la misma cantidad de números de las dos clases.

Ahora bien, notemos que la diferencia entre un número pequeño y el número grande que le sigue (moviéndonos en sentido horario) es igual a la suma de los $d_i$ que hay entre ellos. Por lo tanto, sumando todos los $d_i$ positivos, obtenemos la suma de todos los números grandes menos la suma de todos los números pequeños, que por el enunciado es igual a $1810$. Esta suma también es igual a $a+2b$. Despejando y usando $(**)$, obtenemos $a = 1810-2b$, $c = 1810-2d$. Reemplazando en $(*)$, nos queda $3620 - b - d = 2009$, es decir $b+d = 1611$, luego $a+c = 398$.

Ahora, observemos que $a_i$ y $a_{i+1}$ tienen distinta paridad si y sólo si $d_i$ es impar. Pongamos una marquita roja sobre cada $d_i$ impar. Como acabamos de probar que exactamente $398$ de los $d_i$ son impares, estas marquitas nos dividen la circunferencia en $398$ sectores de modo que cada sector contiene al menos uno de los $a_i$, y la paridad de los números se va alternando con los sectores (o sea, en un sector son todos pares, en el siguiente todos impares, y así). De esto se deduce que hay al menos $199$ números impares y al menos $199$ números pares en la circunferencia, luego la cantidad de números impares tiene que ser un entero entre $199$ y $2009-199 = 1810$.

Veamos que todas ellas son posibles. Sean $s_1, s_2, ..., s_{398}$ la cantidad de $a_i$ que contiene cada sector determinado por las marquitas rojas. Dado $1 \leq k \leq 1612$, es claro que podemos distribuir las marquitas rojas de modo que $s_1 = s_2 = ... = s_{396} = 1$, $s_{397} = k$, $s_{398} = 1613-k$. Los $d_i$ pares los podemos distribuir a nuestro antojo. Ahora sólo basta elegir el $a_1$ convenientemente para que los sectores $s_j$ con $j$ impar sean los que corresponden a números impares, y vamos a tener $198+k$ números impares en total. Este número está entre $199$ y $1810$, como queríamos.
Queda Elegantemente Demostrado

Responder