Problema 3 Nivel 1 Mayo 2019

[Turko Arias]

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.

[Fran5]

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.