Cono Sur 2006 P4

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 157
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Cono Sur 2006 P4

Mensaje sin leer por Matías » Mié 25 Jul, 2018 6:47 pm

En un pizarrón Daniel escribió, de arriba hacia abajo, una lista de números enteros positivos menores o iguales que $10$. Al lado de cada número de la lista de Daniel, Martín anotó la cantidad de veces que ese número figuraba en la lista de Daniel y así obtuvo una lista de la misma longitud.
Si se lee la lista de Martín de abajo hacia arriba se obtiene la misma lista de números que escribió Daniel de arriba hacia abajo. Hallar la longitud máxima que puede tener la lista de Daniel.

Avatar de Usuario
Joacoini

OFO - Medalla de Plata
Mensajes: 109
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 1
Nivel: 2
Ubicación: Ciudad Gotica

Re: Cono Sur 2006 P4

Mensaje sin leer por Joacoini » Jue 26 Jul, 2018 2:07 am

Spoiler: mostrar
Llamamos lista $D$ a la lista de Daniel, $D_i$ al número que aparece en la posición $i$ contando de arriba hacia abajo en la lista $D$, $D'_i$ al número que aparece en la posición $i$ contando de abajo hacia arriba en la lista $D$, $C_i$ a la cantidad de veces que aparece el número $i$ y $n$ la cantidad de números de la lista.
$D'_i=C_{D_i}$ y $D_i=C_{D'_i}$

Supongamos que el número $C_a=b$ y $a\neq b$, si $D_i=a\Rightarrow D'_i=b\Rightarrow C_b=a$ por lo tanto si $D_j=b\Rightarrow D'_j=a$ entoncea por cada $b$ en la lista hay una $a$ y viceversa entonces $C_a=C_b\Rightarrow a=b$ contradicción, por lo tanto $C_a=a$ para cualquier número de la lista lo que se traduce en $D_i=D'_i$.

Si $n$ es par y $a$ un número de la lista entonces la cantidad de veces que aparece $a$ antes de $D_{n/2}$ inclusive ($b$) es la misma que la cantidad de veces que aparece $a$ después de $D_{n/2+1}$ inclusive por lo que $C_a=2b=a$.

Si $n=2m+1$ y $a$ un número tal que $D_{m+1}=a$, la cantidad de veces que aparece $a$ antes de $D_{m}$ inclusive ($b$) es la misma que la cantidad de veces que aparece $a$ después de $D_{m+2}$ inclusive por lo que $C_a=2b+1=a$.

Si $n=2m+1$ y $a$ un número tal que $D_{m+1}\neq a$, la cantidad de veces que aparece $a$ antes de $D_{m}$ inclusive ($b$) es la misma que la cantidad de veces que aparece $a$ después de $D_{m+2}$ inclusive por lo que $C_a=2b=a$.

Queda demostrado que como mucho hay un tipo de número impar en la lista y es cuando la lista tiene una cantidad impar de elementos como $C_a=a$ nos es conveniente que ese número impar sea $9$ y veamos en el siguiente ejemplo que todos los números pares pueden aparecer en la lista.
$10; 10; 10; 10; 10; 8; 8; 8; 8; 6; 6; 6; 4; 4; 2; 9; 9; 9; 9; 9; 9; 9; 9; 9; 2; 4; 4; 6; 6; 6; 8; 8; 8; 8; 10; 10; 10; 10; 10$

La máxima cantidad de números en la lista es $10+8+6+4+2+9=39$
NO HAY ANÁLISIS.

Responder