IMO 2014 Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

IMO 2014 Problema 2

Mensaje sin leer por Matías V5 »

Sea [math] un entero. Consideremos un tablero de tamaño [math] formado por [math] cuadrados unitarios. Una configuración de [math] fichas en este tablero se dice que es pacífica si en cada fila y en cada columna hay exactamente una ficha. Halle el mayor entero positivo [math] tal que, para cada configuración pacífica de [math] fichas, existe un cuadrado de tamaño [math] sin fichas en sus [math] cuadrados unitarios.
1  
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: IMO 2014 Problema 2

Mensaje sin leer por usuario250 »

Spoiler: mostrar
El ejemplo es trivial. Para la justificación hay que fijarse en las n-k filas y las n-k columnas que no contienen al cuadrado. como esas n-k filas pueden tener como mucho una ficha y lo mismo con las n-k columnas, entonces 2(n-k)>=n. por lo que n>=2k.
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: IMO 2014 Problema 2

Mensaje sin leer por Martín Vacas Vignolo »

Ni en pedo Pico... Para [math] es [math]...

* _ _ _
_ _ * _
_ * _ _
_ _ _ *
[math]
Avatar de Usuario
Caro - V3

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 357
Registrado: Sab 16 Oct, 2010 4:20 pm
Medallas: 2
Nivel: Exolímpico

Re: IMO 2014 Problema 2

Mensaje sin leer por Caro - V3 »

Creo que la solución viene por este lado...
Spoiler: mostrar
Defino una tira de tamaño [math] como un conjunto de [math] filas consecutivas en el tablero.
Digo que una columna está tapada en una tira si la ficha de esa columna está en la tira.

Tomemos una tira de tamaño [math] que tenga la primer columna tapada (tiene que existir).
Sabemos que tiene que haber exactamente [math] fichas en la tira (una por fila).
Si en la tira hay [math] columnas no tapadas, entonces encontramos un cuadrado de [math] sin fichas en sus [math] casillas.
Al ser [math], siempre se puede encontrar este cuadrado.
IMO2014P2.png
(Ojo, no es necesariamente así como queda, esta imagen es un ejemplo.)
Conclusión: si [math] siempre se puede encontrar un cuadrado de [math] sin fichas en sus [math] casillas.

Ahora hay que probar que si [math] entonces existe una configuración pacífica de las fichas que no deja huecos de [math]. Para esto basta con dar la distribución para cada [math].
Sea [math].
Tomemos un tablero de [math] y dividámoslo en bloques de [math].
En el bloque ([math],[math]) (contando como matemáticos) poner la ficha en la casilla ([math],[math]) del bloque.

Ahora se pone el tablero de [math] arriba del que marcamos recién. Las fichas que quedan adentro del tablero de [math] las dejamos ahí. Si faltan cubrir algunas filas/columnas, ponemos fichas donde haga falta.
IMO2014P2(b).png
Si en el grande no se podía encontrar un hueco de [math], acá tampoco.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Guía de [math]: sirve para escribir ecuaciones como [math]
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: IMO 2014 Problema 2

Mensaje sin leer por usuario250 »

Ahhh leí otro problema a las apuradas. pensaré el verdadero problema entonces.
karupayun
Mensajes: 4
Registrado: Mié 09 Jul, 2014 2:50 pm
Nivel: Exolímpico

Re: IMO 2014 Problema 2

Mensaje sin leer por karupayun »

La pseudo-solución de Caro es re linda.

Voy a intentar aportar algo a la primera parte que me parece dificil de entender.
Spoiler: mostrar
Sea [math] .Veamos que sin importar como esté distribuída la configuración de [math] fichas, existe un cuadrado de [math] que no tiene ninguna ficha.

Sea [math] la fila de la ficha que está en la 1er columna. Agarro la fila [math] y las [math] filas inferiores o superiores (siempre puedo hacer eso, puesto que [math] (**) )

Nos quedo un conjunto de [math] filas (tira de [math] la llamo Caro), y trazamos el sub-tablero de [math] formado por esas [math] filas y las [math] columnas sin contar la primera del tablero.

- Como [math], podemos dividir ese tablero de [math] en, al menos, [math] tableritos de [math].

- En esos [math] tableros puede haber [math] fichas a lo sumo (1 por cada fila menos 1 por la ya usada en la fila [math] ). Por lo tanto en uno de esos tableros de [math] no hay ninguna ficha, demostrando lo pedido.



(**) [math] (lo cuál para todo p, si quieren formalidad se puede aplicar cuadrática) (**)



-- Lo único que falta demostrar es que existe una configuración de [math], tal que no existe un cuadrado de [math] sin ninguna ficha. La configuración es fácil de encontrar, el problema es la demostración, todas las demostraciones que se me ocurren son largas y tediosas, espero el aporte de algún Prillo.
fleschler.ian

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Jurado-OFO 2018
OFO - Jurado-OFO 2019
Mensajes: 88
Registrado: Vie 05 Oct, 2012 6:40 pm
Medallas: 6
Nivel: Exolímpico

Re: IMO 2014 Problema 2

Mensaje sin leer por fleschler.ian »

Solución:
Spoiler: mostrar
Sea [math] el mayor entero positivo tal que, para cada configuración pacífica de [math] fichas, existe un cuadrado de tamaño [math] sin fichas en sus [math] cuadrados unitarios. Vamos a demostrar que [math].
  • [1][math]

    Vamos a demostrar esto construyendo un ejemplo en el cual todo subtablero de [math] tiene una ficha en al menos una de sus casillas.
    Denotamos [math] a la ficha que se encuentra en la columna [math] y la fila [math]. Donde el [math] es la casilla de más arriba a la izquierda.
    Colocaremos las fichas de la siguiente forma: Los números de las columnas de las fichas que están en las primeras [math] filas son, en orden, los números entre [math] y [math] que tienen resto [math] en la división por [math]. Es decir, hay fichas en [math].
    Los números de las columnas de las fichas que estan en las segundas [math] filas son, en orden, los números entre [math] y [math] que tienen resto [math] en la división por [math]. Es decir, hay fichas en [math]. Y así siguiendo.
    Aca se muestran [math], [math] y [math]:
    12022004_1075939425751060_45429545_n.jpg
    No nos detendremos en la demostración de que este ejemplo funciona ahora (ya que son muchas cuentas). La veremos al final de la solución.

    [2] De un tablero de [math] existe un subtablero de [math] con exactamente [math] fichas.

    Dividamos el tablero de [math] en una columna de [math] y un subtablero de [math]. Existe una fila de alguno de los bordes del subtablero de [math] que contiene una ficha. Ya que en caso contrario necesitaríamos que la columna que agarramos tenga dos fichas, y eso no puede pasar.
    Recortemos la fila que contiene una ficha.
    Ahora tenemos [math] subtableros; una columna de [math], un subtablero de [math] y una fila de [math]. Como la fila y la columna tenían exactamente una ficha entonces el subtablero de [math] tiene [math] fichas que era lo que quería demostrar.

    [3][math]

    Por [2] existe un subtablero de [math] con [math] fichas.
    Si dividimos al subtablero de [math] en [math] subtableritos de [math] como hay mas subtableritos que fichas, por palomar al menos un subtablerito de [math] no tendrá ninguna ficha. Que era lo que queríamos probar.

    [4] Digamos que una configuración feliz de [math], es una configuración pacifica de [math] a la que le sacamos una ficha. Sea [math] el mayor entero tal que, para toda configuración feliz de [math], existe un subtablero de [math] sin ninguna ficha en su interior. Entonces [math].

    Esto se observa fácilmente ya que inicialmente (antes de sacar una ficha) teníamos al menos un subtablero de [math] sin ninguna ficha. Y al sacar una ficha ese tablero que teníamos seguirá estando.

    [5] [math]

    Por [2] existe un subtablero de [math] con [math] fichas en su interior, es decir, una configuración feliz de [math]. Sabemos que [math] porque esta configuración feliz formaba parte del tablero original de [math].
    Por [4] [math]. Entonces podemos concluir [math] que era lo que queríamos demostrar.

    [6] [math].
    Obtenemos esto juntando [1], [3] y [5].
Partiendo desde [6] obtenemos que, si [math] entonces [math].
Por lo tanto [math]. Que era lo que queríamos demostrar.
Demostración de que el ejemplo anda:
Spoiler: mostrar
Para demostrar que el ejemplo funciona veremos que:
  • No hay [math] fichas en el mismo subtablero de [math].
  • La cantidad de subtableros de [math] en los que aparece cada ficha menos la cantidad de subtableros de [math] en los que aparecen dos fichas; es la cantidad total de subtableros de [math] que se pueden elegir de nuestro tablero de [math].
Esas dos cosas implicarían directamente que el ejemplo funciona, ya que por un lado contamos la cantidad de subtableros que contienen al menos una ficha y por otro lado contamos la cantidad de subtableros que hay. Si vemos que nos dan lo mismo habremos demostrado que el ejemplo funciona.
Dividamos al tablero de [math] en [math] subtableros de [math].
Digamos que un subtablero de [math] es lindo si pertenece a esa división.
Por la forma en la que estan elegidas las ubicaciones de las fichas cada subtablero lindo de [math] tiene exactamente una ficha.
Digamos que dos fichas son vecinas si los subtableros lindos en los que están comparten vértice o lado. Digamos que son vecinas por lado si los subtableros lindos a los que pertenecen comparten lado.
Es claro que no hay un subtablero de [math] que contenga a dos fichas que no son vecinas.
Dejo como ejercicio para el lector ver que no hay un subtablero de [math] que contiene dos casillas vecinas por lado. Que solo son vecinas con la que se encuentra en el subtablero de arriba a la derecha y de abajo a la izquierda (y en el caso en el que existe un subtablero de [math] que las contenga, se encuentran en los extremos de este). Parte directo de la definición de la ubicación de las fichas.
Habiendo visto esto ultimo, es inmediato que no hay [math] fichas en el mismo subtablero de [math]. Ya que tendría que incluir fichas [math] de subtableros lindos distintos, que se encuentran en diagonal. Por lo tanto la diagonal del menor subtablero que incluya a las [math] sería mas grande que la diagonal del subtablero de [math]. Ergo no existe ningún subtablero de [math] que contenga a [math] fichas.

Contemos cuantos hay que contienen a [math] fichas. Como bien dijimos antes las fichas tenían que estar en los extremos del subtablero de [math] . Como una estaba arriba a la derecha de la otra entonces la cantidad de subtableros que existen que contienen a [math] fichas, está determinado por la cantidad de fichas que existen que tienen una ficha que está en el subtablero lindo de arriba a la derecha. Que es lo mismo que contar la cantidad de subtableros lindos tales que exista el subtablero lindo de arriba a la derecha. Esa cantidad da [math].

Contemos por un lado en cuantos subtableros están las fichas de los subtableros lindos de las puntas. Dos de ellas están en [math], las otras dos están en [math].
Por otro lado las de los bordes (que no son puntas) suman [math]. (La que esta en la segunda columna aparece en [math] subtableritos, la que esta en la tercera columna aparece en [math] subtableritos, etc. Lo mismo con las filas.)
Ahora contemos las del medio. Hay [math] fichas en los subtableros lindos del medio. Cada una de las cuales aparece en [math] subtableritos.
Hagamos la cuenta total, que nos dara cuantos subtableritos de [math] tienen al menos una ficha.
Esta es: [math]
[math]
[math]
[math].

Ahora nos queda ver que esa es la cantidad de subtableritos de [math] que hay. Podemos contar la cantidad de elecciones que tenemos de la esquina superior izquierda, ya que esto nos determina el subtablero. La podemos elegir de todo el cuadrado de [math] pegado a la esquina superior izquierda. Esas son [math] elecciones posibles.

Ahora nos queda ver que [math] nos da [math].
[math]
[math].
Como dan lo mismo nuestro ejemplo funciona. FIN.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
1  
Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 68
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario

Re: IMO 2014 Problema 2

Mensaje sin leer por Fran2001 »

La demostración del ejemplo ya está, pero quiero dar una demostración más simple que la de fleschler.ian del lado izquierdo de la desigualdad:
Spoiler: mostrar
El mayor $k$ es el que cumple que $k^2<n\leqslant (k+1)^2$
Acá va:
Spoiler: mostrar
Vamos a demostrar que si $k^2<n$ entonces existe un cuadrado de $k\times k$ sin fichas
Para esto tomemos un subtablero de $k\times n$ en el que haya una ficha en la primera columna
Para poder tapar todos los cuadrados de $k\times k$ tenemos que poner al menos una ficha cada $k$ columnas consecutivas en ese subtablero, es decir, al menos $\frac nk$ fichas
Como $k^2<n$; tenemos que $\frac nk>k$
Entonces tenemos que poner al menos $k+1$ fichas en $k$ filas, lo que por Palomar nos lleva a tener al menos una fila con más de una ficha, lo que es una contradicción
Por lo tanto, si $k^2<n$ siempre tendremos un cuadrado de $k\times k$ sin fichas en su interior
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4
Responder