ONEM 2019 - Fase 2 - Nivel 1 - P10

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

OFO - Mención-OFO 2019
Mensajes: 191
Registrado: Mar 31 Jul, 2018 7:39 pm
Medallas: 1

ONEM 2019 - Fase 2 - Nivel 1 - P10

Mensaje sin leer por Nando »

Se pintaron de rojo algunas casillas de un tablero de $9 \times 9$ de tal forma que cada casilla roja es la única casilla roja de su fila o la única casilla roja de su columna (puede ser de ambas). ¿Como máximo cuántas casillas rojas puede haber en el tablero?
Avatar de Usuario
Nando

OFO - Mención-OFO 2019
Mensajes: 191
Registrado: Mar 31 Jul, 2018 7:39 pm
Medallas: 1

Re: ONEM 2019 - Fase 2 - Nivel 1 - P10

Mensaje sin leer por Nando »

Spoiler: mostrar
Por cada casilla pintada podemos trazar dos líneas, una horizontal y otra vertical (para anular las otras casillas), pero como queremos la máxima cantidad de casillas pintadas, por cada casilla pintada solo trazaremos una línea (horizontal o vertical).

Ahora mostraremos que no es posible pintar 17 casillas ya que trazaríamos 17 líneas que podemos distribuir, 9 horizontales y 8 verticales o 8 horizontales y 9 verticales, lo cual no es posible.

Finalmente un ejemplo con 16.
paintnivelzero.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Responder