Nacional 2018 P2 N2

Problemas que aparecen en el Archivo de Enunciados.
tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado FOFO 7 años - Jurado
FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 594
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 10
Nivel: Exolímpico

Nacional 2018 P2 N2

Mensaje sin leer por tuvie » Sab 10 Nov, 2018 7:14 am

Se tienen $n^2$ cajas vacías, cada una de ellas tiene base cuadrada. La altura y el ancho de cada caja son números enteros entre $1$ y $n$ inclusive, y no hay dos cajas iguales. Una caja cabe dentro de otra si su altura y su ancho son menores y ademas alguna de sus medidas es menor por al menos $2$ unidades. De este modo, podemos formar sucesiones de cajas (la primera dentro de la segunda, la segunda dentro de la tercera, y así siguiendo). Ponemos cada una de estas sucesiones en un estante distinto. ¿Cuantos estantes se necesitan para guardar, con certeza, todas las cajas?

Avatar de Usuario
BrunoDS

OFO - Medalla de Plata OFO - Medalla de Oro
Mensajes: 96
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 2
Nivel: 3
Ubicación: Martínez

Re: Nacional 2018 P2 N2

Mensaje sin leer por BrunoDS » Dom 09 Dic, 2018 10:50 am

Spoiler: mostrar
Sea $(a,b)$ una caja de ancho $a$ y altura $b$.

Veamos que con $3n-2$ estantes es posible guardar todas las $n^2$ cajas.
Para eso, a cada caja $(a,b)$, la metemos dentro de la caja $(a+1,b+2)$. De esta manera, es claro que cada caja cabe dentro de la siguiente.
Ahora, contamos cuántos estantes tenemos, contando sólo la primera caja de cada estante (la más chica de cada estante). Tenemos $n$ cajas de la forma $(1,y)$, otras $n-1$ cajas de la forma $(x,1)$ (con $x\geq2$) y otras $n-1$ cajas de la forma $(i,2)$ (con $i\geq2$). Así, al sumarle $(a+1,b+2)$ a cada caja recorremos todas las $n^2$ cajas y en total usamos $n+n-1+n-1=3n-2$ estantes.

Ahora, para demostrar que se necesitan como mínimo $3n-2$ estantes, notemos que si una caja está dentro de otra, entonces la suma del ancho y la altura de la caja grande debe ser al menos $3$ unidades más grande que la suma del ancho y la altura de la caja chica (ya que una de las dos dimensiones debe dismiunuir en al menos $2$ y la otra en al menos $1$).
Luego, si contamos la cantidad de cajas cuya altura y ancho suman $n$, $n+1$ y $n+2$, obtenemos que son $(n-1)+(n)+(n-1)=3n-2$ y además ninguna de estas cajas puede ir dentro de otra, ya que la diferencia es a lo sumo $n+2-n=2$. Luego, necesitamos al menos $3n-2$ estantes.

2  
"No se olviden de entregar la prueba antes de irse..."

Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial
Mensajes: 15
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 1
Nivel: 2

Re: Nacional 2018 P2 N2

Mensaje sin leer por NPCPepe » Mar 15 Oct, 2019 8:48 pm

El enunciado tiene una contradiccion, no puede haber $n^2$ cajas de tamaño distinto si solo pueden tener 2 medidas entre 1 y n, por que si habria $n^2$ cajas distintas entonces habria 2 cajas con 1 de ancho y 1 de alto 2 con 2 y 2 y asi ademas de las cajas posibles

Responder