SOLUCION PROBLEMA REGIONAL OMMCH

[pic 1]

Solucion

Hechos evidentes

• No debe existir un vertice  que sea compartido por 4 cuadrados coloreados al mismo tiempo:

• [pic 2]
• Cuando eso pasa se dice que ese punto (vertice) esta ahogado.

• Es un cuadrado de 7x7 cuyos bordes están coloreados
• Quedan 25 cuadros por colorear
• Demostrar que no se pueden colorear 17 cuadrados (de 25) sin que quede ningún punto ahogado.
• Encontrar una manera de colorear 163 cuadros si ahogar ningún punto.

Resolucion del problema

• Para este problema supondremos que si es posible llenar esos 17 cuadros sin ahogar puntos.

• Como se podrá apreciar en la primera imagen, los bordes de aquel cuadrado de 7x7por lo que solo queda en su interior un cuadrado blanco de 5x5:
• [pic 3]
• Como se podrá apreciar, si coloreamos las 4 esquinas del cuadrado de 5x5 estariamos ahogando 4 puntos, esto se opone al objetivo, por lo tanto, no se colorearan esas esquinas (lo marcaremos con rojo)
• [pic 4]
• Ahora, solo quedan 21 cuadros posibles de 17 a colorear.
• Entre ellos están estas 4 areas verdes formadas de 3 cuadros cada una,  como se habran dado cuenta, intentare colorear la mayor cantidad de cuadros en cada área, es decir 2, ya que si coloreo 3, estaría ahogando forzosamente algún punto que comparta con el margen (cuadro de 7x7).
• Existen tres maneras de hacer esto (donde verde y gris significa coloreado y rojo significa sin colorear):

• [pic 5]
• [pic 6]
• [pic 7] 

• Como se habran dado cuenta la primera es la correcta, ya que no ahoga ningún punto a diferencia de la segunda y tercera que si lo hacen.
• Procedemos a colorear esas alas como el primer ejemplo
• [pic 8]
• Ya hemos coloreado 8 cuadros, descartado 8 y quedan 9 mas por colorear
• Nuestro objetivo era colorear 17 cuadros sin ahogar ningún punto, y dado a la stuacion contada en el punto anterior, procedemos a colorear los 9 cuadros restantes para asi cumplir con la condición “COLOREAR 17 CUADROS”
• [pic 9]
• Como pueden apreciar, se han coloreado los 17 cuadros planteados, pero ahogamos 4 puntos (esas bolas moradas), por lo tanto, acabamos de demostrar por contradicción que es imposible colorear 17 cuadros sin ahogar un punto.

EXTRA

AQUÍ ESTA EL CASO DONDE 16 CUADROS SON COLOREADOS  SIN AHOGAR NINGUN PUNTO  (SE COLOREAN  DE AZUL)

[pic 10]

...