Torneo de las Ciudades Marzo 2012 P7 Nivel Mayor

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nacho

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Torneo de las Ciudades Marzo 2012 P7 Nivel Mayor

Mensaje sin leer por Nacho » Lun 19 Mar, 2012 11:32 pm

Konstantin tiene una pila de [math] piedras. En cada movida, elige una pila y la divide en dos más chicas hasta tener [math] pilas de una piedra cada una. Demostrar que:

a) En algún momento, entre las pilas habrá [math] pilas que contienen en total exactamente [math] piedras. (6 puntos).

b) En algún momento, entre las pilas habrá [math] pilas que contienen en total exactamente [math] piedras. (3 puntos).

c) Konstantin puede mover de modo que en ningún momento haya entre las pilas [math] pilas que contengan en total exactamente [math] piedras. (3 puntos).
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Joacoini

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

Re: Torneo de las Ciudades Marzo 2012 P7 Nivel Mayor

Mensaje sin leer por Joacoini » Dom 08 Abr, 2018 11:42 am

Solución Oficial
Spoiler: mostrar
a) En algún momento tenemos exactamente $70$ pilas. Al menos $40$ de ellas contienen exactamente $1$ piedra cada una, pues en otro caso el número de piedras es al menos $39+2\times 31=101$. Ademas de esas $40$ pilas tenemos exactamente $30$ pilas que contienen exactamente $60$ piedras.

b) Llamaremos $k$ pilas que contienen exactamente $2k+20$ piedras una colección buena.
Afirmamos que si $k\geq 23$, una colección buena contiene o bien $1$ pila con exactamente $2$ piedras o bien $2$ pilas con exactamente $1$ piedra casa una. En caso contrario el número total de piedras en la colección es al menos $1+3(k-1)=3k-2$, que es estrictamente mayor a $2k+20$ cuando $k\geq 23$.
Ahora cualquier partición de la pila original en $40$ pilas resulta una colección buena con $k=40$. De aquí podemos obtener una colección buena con $k=39$, o bien quitando una pila con exactamente $2$ piedras. Del mismo modo podemos obtener colecciones buenas descendiendo hasta $k=22$, con un total de exactamente $64$ piedras. Afirmamos que existe $2$ o más pilas que contienen en total exactamente $4$ piedras. Supongamos que no es el caso. Si no hay pilas con exactamente $1$ piedra, entonces el número total de piedras en la colección es al menos $3+4\times 19>64$.
Así la afirmación queda justificada. Ahora quitamos esas $4$ piedras y obtenemos $60$ piedras en a lo sumo $20$ pilas. Las divisiones eventuales de esas pilas nos llevan el número de pilas a $20$, mientras qué el número total de piedras es $60$

c) Separamos pilas de $3$ piedras hasta tener $32$ pilas de $3$ piedras y $1$ pila de $4$ piedras. A lo largo de este proceso, exactamente una pila contiene una cantidad de piedras no divisible por $3$. Si incluimos es pila el número total no puede ser $60$. Si no la incluimos el total de $19$ pilas de $3$ es solo de $57$ piedras. Ahora separamos la pila de $4$ en $2$ pilas de $2$ piedras, así cada pila contiene a lo sumo $3$ piedras, de modo que $19$ pilas pueden contener a lo sumo $57$ piedras. Las divisiones posteriores no cambian esta situación
NO HAY ANÁLISIS.

Responder