Selectivo IMO 2009 - Puerto Rico - Problema 6

Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Selectivo IMO 2009 - Puerto Rico - Problema 6

Mensaje sin leer por Violeta »

Se tiene un cuadrado [math], cuyos [math] cuadritos están coloreados como un tablero de ajedrez: alternando entre blanco y negro. La casilla superior izquierda es negra.

La operación permitida es elegir un rectángulo [math] o [math] que todavía tenga tres cuadritos blancos y pintar los cuadritos blancos en ese rectángulo de negro.

Encontrar todos los [math] para los cual es posible colorear de negro todo el tablero en una cantidad finita de operaciones.
Para todo [math], existen [math] primos en sucesión aritmética.
Avatar de Usuario
Johanna

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2017 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 65
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 9
Nivel: Exolímpico

Re: Selectivo IMO 2009 - Puerto Rico - Problema 6

Mensaje sin leer por Johanna »

Spoiler: mostrar
Notemos que en cada paso pintamos [math] casillas de negro por lo que la cantidad de casillas blancas tiene que ser múltiplo de [math] entonces si [math], [math] y si [math], [math] [math]
Es facil construir el ejemplo para n=6m
Faltarian construir los ejemplos para [math] y [math].
La idea para construirlos seria proceder inductivamente viendo que un tablero de si tengo un tablero de [math] puedo agregar dos columnas y dos filas para llegar a uno de [math] y en efecto esas dos filas y columnas que agregamos se pueden colorear de negro. Despues veamos que si a un tablero de [math] le agrego dos filas arriba y dos filas abajo y dos columnas a izquiarda y dos a derecha queda un tablero de [math] donde podemos colorear el tablero de adentro y ademas se puede colorear el borde.
Responder