Selectivo Cono 2022 P2

Problemas que aparecen en el Archivo de Enunciados.
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
Mensajes: 1925
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Selectivo Cono 2022 P2

Mensaje sin leer por Gianni De Rico »

Sea $k$ un entero mayor que $1$. Hallar el menor entero positivo $n$ para el que en un tablero de $n\times n$ se pueden pintar de negro algunas casillas de modo tal que cada fila y cada columna contenga exactamente $k$ casillas negras y no haya dos casillas negras que tengan un lado o un vértice en común.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Avatar de Usuario
ésta

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

Re: Selectivo Cono 2022 P2

Mensaje sin leer por ésta »

Cota:
Spoiler: mostrar
Supongamos que exista una coloración válida para $n$ y $k$. Es claro que $n \geq k$ y como $k > 1$ tenemos $n \geq 2$. Luego hay una segunda fila en el tablero y hay una columna que tiene una casilla pintada en la segunda fila. Miramos esa columna y una adyacente (siempre existe al menos una). Entre estas dos columnas, tenemos que tener $2k$ casillas pintadas, cada fila tiene a lo sumo una y no hay dos filas adyacentes con casillas pintadas. Por lo tanto, si miramos las filas de las casillas pintadas, de arriba hacia abajo, la primera está en la fila $2$, la segunda por lo menos en la fila $4$, la tercera por lo menos en la fila $6$ y así, la $2k$-ésima está por lo menos en la fila $4k$. Por lo que $n \geq 4k$.
Ejemplo:
Spoiler: mostrar
bitmap.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
3  
Imagen
Responder