(A) Problema para ajudar na escola: Colorindo quadradinhos

Problema
(A partir do 6º ano do E. F. – Nível de dificuldade: Médio)

(ONEM – 2004) Nove quadradinhos de uma malha quadriculada [tex]3 \times 3[/tex], como a mostrada na figura abaixo, devem ser pintados de forma que, em cada linha, em cada coluna e em cada uma das duas diagonais da malha, não haja quadradinhos de uma mesma cor.
Qual a menor quantidade de cores necessárias para que a pintura possa ser executada?

Solução

• Vamos iniciar a definição das cores pelo quadradinho central, já que este é o que afeta mais posições da malha. Vamos supor que [tex]\textcolor{red}{A}[/tex] seja a sua cor.

[tex]\hspace{3cm}\begin{array}{|c|c|c|}
\hline
\, \, \, & \, \, \, & \, \, \, \\
\hline
&\textcolor{red}{A} &\\
\hline
\, \, \, & &\\
\hline
\end{array} \, \, [/tex]

• Observando os quatro quadradinhos dos cantos da malha, vemos que dois deles não podem ter a mesma cor e nenhum dos quatro pode ter a cor [tex]\textcolor{red}{A}[/tex], pois isso implicaria que uma linha ou uma coluna ou uma diagonal teria(m) quadradinhos de uma mesma cor. Logo, precisaremos de mais quatro cores diferentes, digamos: [tex]\textcolor{#00CD00}{B}[/tex], [tex]\textcolor{#FF00FF}{C}[/tex], [tex]\textcolor{blue}{D}[/tex] e [tex]\textcolor{#A0522D}{E}.[/tex]

[tex]\hspace{3cm}\begin{array}{|c|c|c|}
\hline
\textcolor{#00CD00}{B}& \, \, \, &\textcolor{#FF00FF}{C}\\
\hline
&\textcolor{red}{A} &\\
\hline
\textcolor{blue}{D}& &\textcolor{#A0522D}{E}\\
\hline
\end{array} \, \, [/tex]

• Agora, com um exemplo, podemos verificar que as cinco cores definidas são suficientes para colorirmos a malha de acordo com as restrições impostas pelo problema; vejam:

[tex]\hspace{3cm}\begin{array}{|c|c|c|}
\hline
\textcolor{#00CD00}{B}&\textcolor{#A0522D}{E} &\textcolor{#FF00FF}{C}\\
\hline
\textcolor{#FF00FF}{C}&\textcolor{red}{A} &\textcolor{blue}{D}\\
\hline
\textcolor{blue}{D}& \textcolor{#00CD00}{B} &\textcolor{#A0522D}{E}\\
\hline
\end{array} \, \, [/tex]

Assim, com cinco cores conseguimos pintar os quadradinhos da malha, de acordo com as regras estabelecidas, e, com menos de cinco cores, não conseguimos fazê-lo. Portanto, a menor quantidade de cores necessárias para que a pintura possa ser executada é cinco.

Solução elaborada pelos Moderadores do Blog.