Selectivo de IMO 2011 - Problema 6

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

Selectivo de IMO 2011 - Problema 6

Mensaje sin leer por Matías V5 »

Cada casilla de un tablero de [math] se colorea de rojo o de azul de modo que entre todos los cuadrados de [math] de este tablero se encuentren presentes todas las posibles coloraciones de cuadrados de [math] con rojo y azul (coloraciones que se obtienen una de otra por rotación o reflexión se consideran distintas).
a) Hallar el menor valor posible de [math].
b) Para ese valor mínimo de [math], hallar el menor valor posible de cuadrados rojos.
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
Mariano Juncal

Colaborador-Varias OFO - Medalla de Bronce-OFO 2015
Mensajes: 38
Registrado: Sab 16 Oct, 2010 6:49 pm
Medallas: 2

Re: Selectivo de IMO 2011 - Problema 6

Mensaje sin leer por Mariano Juncal »

Spoiler: mostrar
Bueno, asignamos a cada casillero una puntuacion, que es en cuántos cuadraditos de 2x2 aparece. Los casilleros de la esquina valen 1, los de los costados valen 2, y los del cuadradito de 3x3 del centro valen 4. Como hay 16 cuadraditos de 2x2, con 4 cuadraditos de 1x1 adentro, la puntuacion total es de 64, 32 puntos para el azul y 32 puntos para el rojo ya que aparecen todas las combinaciones. Al tener 32 puntos el rojo, debe haber minimo 8 rojos. Veamos que el minimo no es 8. Si fuera 8, habría 8 cuadraditos de 4 puntos pintados de rojo. Entonces la fila de arriba seria todo A y la de abajo todo A. Pero de los 4 cuadraditos de 2x2 de arriba de todo, uno debe ser todo A ya que hay sólo 4 formas de pintar posibles un cuadradito de 2x2 si ya está pintada de A la fila de arriba. Análogamente, uno de los cuadraditos de abajo tiene que ser todo A, pero no puede haber dos así que con 8 no se puede.

Vamos a ver que con 9 no se puede. Si se pudiera, los cuadraditos que valen 1 deberían ser azules, ya que de otro modo para que la suma dé 32 (0 modulo 4) debería haber mínimo otro de 1, y uno de 2 (o dos de 1). Eso es mínimo 3 para sumar 4, y faltan sumar 32-4=28 que los sumas con al menos 7, y ahí tenes mínimo 10. Entonces, las esquinas están pintadas de azul. Como vimos antes, las filas de arriba y abajo no pueden ser todas A, entonces hay al menos un R en una de esas filas (pero no en las esquinas), y lo mismo con las columnas primera y última. Al haber al menos dos R de 2 puntos, tenemos 32- 2x2 = 28, 28/4 = 7, es decir, si queremos que haya sólo 9 rojos, los otros 7 deben valer 4 puntos.

Esto significa que el cuadrado todo rojo debe estar en el cuadradito de 3x3 del medio, ya que de otro modo habria una fila o columna del borde con 2 rojos, y esto sumaría minimo tres R de 2 puntos, porque recordemos que había exactamente una fila del borde con un rojo, y exactamente una columna del borde con un rojo, y las esquinas no pueden ser rojas.

Hay una sola posibilidad (o sea, hay mas pero son rotaciones y/o reflexiones) para pintar el cuadradito de 3x3, y es la siguiente:

R R R
R R A
A R R

Entonces, por ahora nos queda asi la cosa:

A X X X A
X R R R X
X R R A X
X A R R X
A X X X A

Pero fijémonos dos cosas: El único lugar que tiene el cuadradito de 2x2 todo azul es abajo a la izquierda. También, fijémonos los cuadraditos de 2x2 pintados de rojo su primera fila. Ya tenemos:
R R ........ R R ........ R R
R R ........ R A ........ A R

Por lo tanto, la única posibilidad para el cuadradito restante con R R en la primer fila (El que esta mas o menos abajo tirando a la derecha), es:

R R
A A

Con esto, el esquema nos queda así:

A X X X A
X R R R X
X R R A X
A A R R X
A A A A A

Y ya no se puede porque tenemos 5 cuadraditos de 2x2 con A A en su última fila, pero puede haber máximo 4 de estos para que no se repitan (Recordemos que hay 16 cuadraditos de 2x2, y 16 coloraciones, entonces debe haber exactamente uno con cada coloración).
Entonces, la cantidad mínima de rojos es 10, como muestra el siguiente ejemplo:

A R A A A
A R R R A
R R R A R
A A R A A
A R A A A
Última edición por Mariano Juncal el Sab 30 Abr, 2011 12:52 am, editado 1 vez en total.
1  
Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 300
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: Selectivo de IMO 2011 - Problema 6

Mensaje sin leer por ésta »

Una variante de la parte b:
Hallar para todo [math], el menor valor posible de cuadrados rojos.
Imagen
Azul Lihuen

OFO - Jurado-OFO 2016
Mensajes: 20
Registrado: Mié 28 Sep, 2011 7:20 pm
Medallas: 1
Nivel: Exolímpico

Re: Selectivo de IMO 2011 - Problema 6

Mensaje sin leer por Azul Lihuen »

Misma idea y distinto ejemplo(?
Spoiler: mostrar
a) Al igual que Mariano, le asignamos una puntuación a las casillas del tablero, teniendo en cuenta la cantidad de veces que aparece cada casilla en algun cuadradito de 2x2. En un tablero de nxn, las esquinas valen 1, en el cuadrado central (n-2)x(n-2) las casillas valen 4 , y las restantes (n-2)x4 casillas valen 2.

Entonces el 'valor' de un tablero de nxn es 4*(n-2)²+(n-2)*4*2+4=4n²-8n+4.(*)

Hay 16 formas de pintar cuadraditos de 2x2, entonces tenemos 16*4=64 casillas involucradas(?, por lo que igualamos (*) a 64.
4n²-8n+4-64=4n²-8n-60=0, cuyas soluciones son -3 y 5. Claramente, el mínimo valor de n es 5.


b) Como la suma de los valores de las casillas de un tablero de 5x5 es exactamente 64, cada posible coloración de cuadrados de 2x2 aparece exactamente una vez.

• En las coloraciones, las casillas rojas son 32, por lo que el mínimo hasta ahora es 8, que correspondería a 8 casillas de valor 4, es decir, que están en el cuadrado de 3x3 central. Pero si colocamos las 8 casillas rojas en este cuadrado de 3x3, vemos que la casilla azul tiene que estar sí o sí en el centro, porque si no el cuadrado todo rojo aparecería más de una vez y no es posible. Y si la ponemos en el centro, nunca vamos a poder encontrar un cuadrado de 2x2 completamente azul. Entonces, el mínimo no es 8.

• Si el mínimo es 9, esto correspondería a 7 casillas rojas de valor 4 y 2 casillas rojas de valor 2(por lo que las casillas de las esquinas de valor 1 son azules). Entonces, tenemos en el cuadrado central de 3x3 2 casillas azules y 7 rojas. Para que sea posible encontrar un cuadrado todo azul, una de las casillas azules debe estar en una esquina del cuadrado central de 3x3, (o las dos tienen que compartir un lado sin que una sea del centro, pero en ese caso sí o sí una tiene que ser de la esquina y es lo mismo). Además, para que el cuadrado todo rojo no aparezca más de una vez, estas dos casillas deben estar en filas y columnas diferentes (porque si no habría un rectángulo de 2x3 todo rojo). Nos quedan entonces tres posibilidades para el cuadrado central de 3x3(con sus rotaciones y reflexiones):

R R A
R R R
A R R

R R R
R A R
A R R

R R R
R R A
A R R

-En la primera posibilidad está dos veces el cuadrado de 2x2 todo rojo, entonces la descartamos.

-En la segunda posibilidad, el único lugar donde podemos pintar el cuadrado todo azul es en la esquina, y nos queda lo siguiente:

A X X X A
X R R R X
X R A R X
A A R R X
A A X X A

Pero entonces no es posible ubicar al cuadrado R A A R (colores iguales en esquinas opuestas)en ningún lugar.

-En la tercera, también el único lugar donde podemos pintar el cuadrado todo azul es en la esquina, y nos queda así:

A X X X A
X R R R X
X R R A X
A A R R X
A A X X A

Pero entonces no es posible ubicar al cuadrado A R R A (colores iguales en esquinas opuestas)en ningún lugar.

Entonces el mínimo no puede ser 9.


• El menor valor posible de casillas rojas es entonces 10. Por ejemplo:

A A A R A
A R R A A
A R R R A
R R A A R
A R A A A

:)
1  
♥ ^ [math]
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de IMO 2011 - Problema 6

Mensaje sin leer por Gianni De Rico »

Otra demostración de la parte a)
Spoiler: mostrar
Veamos que en un tablero de $t\times t$ hay $(t-s+1)^2$ subtableros de $s\times s$. Si colocamos el subtablero de $s\times s$ en la esquina superior izquierda, nos sobran $t-s+1$ columnas hacia la derecha, por lo tanto, podemos mover el subtablero $t-s+1$ veces hacia la derecha. Análogamente, podemos mover el subtablero $t-s+1$ veces hacia abajo en cada fila, como hay $t-s+1$ subtableros por fila, en total hay $(t-s+1)^2$ subtableros de $s\times s$.

Hay $2^4=16$ posibles coloraciones de un tablero de $2\times 2$, entonces necesitamos que $(n-2+1)^2=(n-1)^2\ge 16=4^2\Rightarrow n=5$ es el mínimo posible.
♪♫ do re mi función lineal ♪♫
Responder