Problema 3 Nivel 1 Mayo 2019

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 284
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Problema 3 Nivel 1 Mayo 2019

Mensaje sin leer por Turko Arias » Vie 26 Jul, 2019 2:59 am

Gus tiene que hacer una lista de $250$ números enteros positivos, no necesariamente distintos, tal que cada número sea igual a la cantidad de números de la lista que son distintos de él. Por ejemplo, si $15$ es un número de la lista entonces la lista contiene $15$ números distintos de $15$. Determinar la máxima cantidad de números distintos que puede contener la lista de Gus.

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 858
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Problema 3 Nivel 1 Mayo 2019

Mensaje sin leer por Fran5 » Dom 28 Jul, 2019 9:28 pm

Pregunta disparadora:
Spoiler: mostrar
Cuántas veces aparece un número $n$ de en la lista?
Idea quemadora:
Spoiler: mostrar
Si $a_n$ es la cantidad de veces que aparece $n$ en la lista, entonces $250 = \sum_{i=1}^{250}a_n$. Cómo es la suma de la derecha? La puedo acotar?
Solución:
Spoiler: mostrar
Tomemos un número $n$ que aparece en la lista. Como hay $250$ números y $n$ son distintos a él, tenemos que $n$ aparece las restantes $250-n$ veces en la lista.

Sea ahora $a_n$ la cantidad de veces que aparece cada número $n$ en la lista. Sabemos que $a_n = 0$ si no aparece, y $a_n = 250-n$ si sí lo hace. Luego, tenemos que $$250 = \sum_{i=1}^{250}a_n,$$ pues no puede haber ningún número mayor a $250$ en la lista.

Si en la lista hay $d$ números distintos, entonces exactamente $d$ de los sumandos $a_n$ son no nulos, con lo cual $$250 = \sum_{i=1}^{250} a_n \geq 1 + 2 + \ldots + d = \frac{d(d+1)}{2},$$ de donde $d \leq 21$.

Finalmente, podemos ver que pueden haber exactamente $21$ números distintos: cada uno de los $20$ números $n$ entre $230$ y $249$ aparece $250 - n$ veces, respectivamente. De este modo $249$ aparece una vez, $248$ dos veces, $\ldots$, $230$ aparece $20$ veces. En este caso hay $210$ números en la lista, con lo cual agregamos $30$ veces el $220$, teniendo $21$ números distintos.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Responder