Nacional 2022 - Nivel 3 - Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 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
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2022 - Nivel 3 - Problema 4

Mensaje sin leer por Monazo »

Consideramos un tablero cuadrado de $1000\times 1000$ con $1000000$ casillas de $1\times 1$. Una ficha colocada en una casilla amenaza a todas las casillas del tablero que están adentro de un cuadrado de $19\times 19$ con centro en la casilla donde está colocada la ficha, y de lados paralelos a los del tablero, excepto las casillas de su misma fila y las de su misma columna. Determinar el máximo número de fichas que se pueden colocar en el tablero de modo que no haya dos que se amenacen.
Soy una Estufa en Piloto
:shock:
Avatar de Usuario
Lean

OFO - Medalla de Bronce-OFO 2023 FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Plata-OFO 2024
Mensajes: 176
Registrado: Vie 20 Ene, 2023 10:38 am
Medallas: 3
Nivel: 3
Ubicación: Quilmes

Re: Nacional 2022 - Nivel 3 - Problema 4

Mensaje sin leer por Lean »

Problema $3$ de la clase de Bruno
Spoiler: mostrar
Si tomamos la casilla $(1,1)$, su radio de amenaza es $9$, por lo que afecta a un cuadrado de $10.10$. Ademas, ninguna casilla ademas de todas las casillas de su misma fila o de su misma columna pueden estar dentro de este cuadrado. Es decir, en este caso, el maximo de fichas de este $10.10$ es $10$, todas las de la fila $1$ o todas de la columna $1$, contando desde arriba hacia abajo y desde la izquierda hacia la derecha.

Continuando este patron que parece ser la mejor, tomando todas las casillas de una columna por ejemplo, la copiamos para todo el tablero de $1000.1000$. Entonces tenemos, $(10.100).(1000/10)=100000$. Ya que un tablero $10.10$ igual inmediatamente a la derecha o abajo no amenazara a ninguna ficha del tablero anterior, esto porque se conserva el radio de $9$ que los separa.

Suponiendo que se pueda para $>100000$ fichas, dividamos el tablero en $100$ tiras de $10.1000$, una tras otra. Como tengo $>100000$, alguna tira tendra $>1000$ por Palomar. Analogamente, dividamos esta tira con $>1000$ casillas en $100$ tiras de cuadrados de $10.10$ y alguno tendra $>10$, absurdo, ya que sabemos que en un tablero de $10.10$ el maximo es $10$.

Por ende, la cantidad es $100000$.
"El mejor número es el 73".
Responder