Nacional 2019 N1 P6

Problemas que aparecen en el Archivo de Enunciados.
LuchoLP

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 191
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Nacional 2019 N1 P6

Mensaje sin leer por LuchoLP » Jue 14 Nov, 2019 10:21 am

En un tablero de $9\times 9$ hay que colorear de rojo algunas casillas, por lo menos una. Para cada coloración, sea $P$ la cantidad de casillas, coloreadas o no, que tienen un número par de casillas vecinas rojas. (Dos casillas son vecinas si tienen un lado común). Dar una coloración del tablero que tenga el menor valor posible de $P$ y demostrar que no puede haber un valor más chico.

ACLARACIÓN: $0$ es par.

axelO
Mensajes: 2
Registrado: Mié 13 Nov, 2019 9:26 pm
Nivel: 1

Re: Nacional 2019 N1 P6

Mensaje sin leer por axelO » Sab 16 Nov, 2019 1:20 pm

Spoiler: mostrar
Primero enumero las casillas del tablero con los números del $1$ al $81$ ,de modo que en la primera fila estén los números del $1$ al $9$ desde la izquierda hacia la derecha en orden creciente.Luego en la segunda fila los números del $10$ al $18$ desde la izquierda hacia la derecha en orden creciente, así hasta en la novena fila en la que enumero las casillas del $73$ al $81$ Desde la izquierda hacia la derecha en orden creciente.
A continuación doy un ejemplo para P=$1$

Si pinto de rojo las siguientes casillas,encuentro un ejemplo:
$1$,$4$,$5$,$8$,$9$,$10$,$21$,$24$,$25$,$30$,$36$,$37$,$41$,$45$,$46$,$52$,$57$,$58$,$61$,$72$,$73$,$74$,$77$,$78$,$81$.

Ahora demuestro que $P\neq0$
Si decimos que P=$0$ estamos diciendo que cada casilla tiene una cantidad impar de casillas vecinas pintadas de rojo.
Veamos que la casilla $1$ tiene una cantidad par de casillas vecinas , de esas casillas vecinas ,deben estar pintadas de rojo una cantidad impar.Ahora veamos que la casilla $11$ tiene $4$ casillas vecinas de las cuales $2$ comparte con la casilla $1$ y de esas $2$ casillas que comparte con la casilla $1$ ,están pintadas de rojo una cantidad impar de casillas, por lo que las $2$ casillas vecinas restantes tienen que tener una cantidad par de casillas pintadas de rojo para que la casilla $11$ no pertenezca a P. Veamos que $11$ también comparte $2$ casillas vecinas con la casilla $21$ , por lo que las casillas vecinas restantes de $21$ tienen que tener una cantidad impar de casillas vecinas pintadas de rojo,luego $21$ comparte $2$ casillas vecinas con $31$ por lo que las casillas vecinas restantes de $31$ tienen que tener una cantidad impar de casillas vecinas pintadas de rojo, luego esto pasa con los números de $2$ dígitos restantes que son de la forma A1 ( A es un dígito y 1 otro) ,tal que $A\geq4$ y $A\leq8$,( A no es $0$,$1$,$2$ o $3$ porque esas opciones ya las analizamos) .
Ahora, como las casillas restantes de $31$ tienen una cantidad par de casillas pintadas de rojo ,las casillas restantes de $41$ tienen una cantidad impar de casillas vecinas pintadas de rojo, las casillas restantes de $51$ tienen una cantidad par de casillas pintadas de rojo, luego $61$ tiene una cantidad impar, $71$ tiene una cantidad par. Pero si las $2$ casillas restantes de $71$ tienen una cantidad par de casillas pintadas de rojo significa también que las $2$ casillas vecinas de la casilla $81$ tienen una cantidad par de casillas vecinas pintadas de rojo y como la casilla $81$ tiene dos casillas vecinas , significa que la casilla $81$ pertenece a P, entonces $P\neq0$,
$P\geq1$[\spoiler]
Última edición por axelO el Lun 18 Nov, 2019 9:14 pm, editado 1 vez en total.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 205
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: Nacional 2019 N1 P6

Mensaje sin leer por BrunZo » Sab 16 Nov, 2019 8:44 pm

Ejemplo:
Spoiler: mostrar
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
\blacksquare & \blacksquare & & & \blacksquare & \blacksquare & & & \blacksquare \\ \hline
& & & & & & & & \blacksquare \\ \hline
& & \blacksquare & \blacksquare & & & \blacksquare & & \\ \hline
\blacksquare & & & & & & \blacksquare & & \\ \hline
\blacksquare & & & & \blacksquare & & & & \blacksquare \\ \hline
& & \blacksquare & & & & & & \blacksquare \\ \hline
& & \blacksquare & & & \blacksquare & \blacksquare & & \\ \hline
\blacksquare & & & & & & & & \\ \hline
\blacksquare & & & \blacksquare & \blacksquare & & & \blacksquare & \blacksquare \\ \hline
\end{array}$$
Donde $P=1$ (la casilla del centro).
Solución 1: (contada en la resolución.)
Spoiler: mostrar
Supongamos que $P=0$, es decir, toda casilla tiene impar cantidad de vecinas pintadas.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
1 & \neq & & & & & & & \\ \hline
\neq & 2 & = & & & & & & \\ \hline
& = & 3 & \neq & & & & & \\ \hline
& & \neq & 4 & = & & & & \\ \hline
& & & = & 5 & \neq & & & \\ \hline
& & & & \neq & 6 & = & & \\ \hline
& & & & & = & 7 & \neq & \\ \hline
& & & & & & \neq & 8 & = \\ \hline
& & & & & & & = & 9 \\ \hline
\end{array}$$
Concentrémonos en la casilla $1$: Es claro que exactamente una de sus dos vecinas debe estar pintada y la otra no, por lo que sus dos vecinas son distintas. Miremos la casilla $2$: Como entre sus vecinas de arriba e izquierda hay exactamente una casilla pintada, entre sus otras dos vecinas hay cero o dos pintadas, es decir, sus vecinas de arriba y abajo son iguales. Fijémonos en la casilla $3$: Como entre sus vecinas de arriba e izquierda hay cero o dos pintadas, entre sus otras dos vecinas hay exactamente una pintada, es decir, son diferentes.
Si así seguimos, obtenemos que las dos vecinas de la casilla $9$ son iguales, lo cual contradice lo supuesto, ya que esta casilla tendría cero o dos vecinas, que es par. Luego $P\geq 1$.
Solución 2: (mía.)
Spoiler: mostrar
Coloreemos el tablero de la siguiente forma:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
1 & \blacksquare & 2 & \blacksquare & 1 & \blacksquare & 2 & \blacksquare & 1 \\ \hline
\blacksquare & & \blacksquare & & \blacksquare && \blacksquare & & \blacksquare \\ \hline
2 & \blacksquare & 1 & \blacksquare & 2 & \blacksquare & 1 & \blacksquare & 2 \\ \hline
\blacksquare & & \blacksquare & & \blacksquare && \blacksquare & & \blacksquare \\ \hline
1 & \blacksquare & 2 & \blacksquare & 1 & \blacksquare & 2 & \blacksquare & 1 \\ \hline
\blacksquare & & \blacksquare & & \blacksquare && \blacksquare & & \blacksquare \\ \hline
2 & \blacksquare & 1 & \blacksquare & 2 & \blacksquare & 1 & \blacksquare & 2 \\ \hline
\blacksquare & & \blacksquare & & \blacksquare && \blacksquare & & \blacksquare \\ \hline
1 & \blacksquare & 2 & \blacksquare & 1 & \blacksquare & 2 & \blacksquare & 1 \\ \hline
\end{array}$$
Sea $T$ la cantidad de casillas negras que se pintan. Es claro que cada una de estas casillas tiene exactamente una casilla $1$ y exactamente una casilla $2$ como vecinas.
De este modo, sea $S_i$ la suma de, para cada casilla con número $i$, la cantidad de vecinas que están pintadas de rojo. Se sigue que
$$S_1=S_2=T$$
Supongamos que $P=0$. Es decir, cada casilla $1$ ó $2$ tiene $1\mod 2$ vecinas pintadas. Y, como hay trece casillas $1$ y doce casillas $2$, entonces
$$S_1\equiv \underbrace{1+1+1+\cdots+1}_{13}\equiv 13\cdot 1\equiv 1\mod 2$$
$$S_2\equiv \underbrace{1+1+1+\cdots+1}_{12}\equiv 12\cdot 1\equiv 0\mod 2$$
Lo cual es una clara contradicción con $S_1=S_2$. Por lo tanto, $P\geq 1$.

Responder