Confinamento Colorido
.
Por Jorge Nuno Silva
Será possível colorir um mapa de Portugal, sem ambiguidades na identificação dos distritos, usando apenas quatro cores?
Fig. 1
Deixamos ao leitor a possibilidade de encontrar tal coloração ou a confirmar num dos muitos mapas do país.
Esta possibilidade é uma ilustração do Teorema das Quatro Cores (T4C), um resultado com uma história dramática, que transcende o âmbito desta nota breve.
Sabemos que qualquer mapa plano, real ou imaginado, pode ser colorido usando, no máximo, quatro cores, evitando ambiguidades (duas regiões diferentes podem partilhar um ponto isolado, mas não uma curva). Vejamos um exemplo mais complexo.
Fig. 2
Neste contexto, queria propor um jogo em que pode participar toda a família.
Consideremos a figura
Fig. 3
De acordo com o T4C, podemos colori-lo com quatro cores, o que ilustramos abaixo.
Fig. 4
Agora imaginemos que temos duas pessoas – o Min e o Max -- que, alternadamente, pintam uma região da sua escolha de acordo com a nossa regra (vizinhos com cores distintas). Imaginemos ainda que o Min quer usar somente as quatro cores para terminarem a tarefa e que o Max quer que seja necessário usar mais. Agora talvez quatro não bastem...
De facto, se jogar bem, o Max pode forçar uma situação do género da ilustrada, donde se conclui que uma quinta cor seria necessária.
Fig. 5
O jogo que eu proponho é então o seguinte.
- Há n lápis de cores diferentes.
- Há um mapa plano.
Dois jogadores, o Min e o Max, alternam a colorir uma região segundo a nossa regra. O Min quer que terminem a tarefa usando as n cores, o Max quer tornar as n cores insuficientes. O primeiro a jogar é o Min.
O Min ganha se colorirem completamente o mapa com as n cores (ou parte delas), o Max ganha se um dos jogadores não conseguir jogar antes de o mapa estar completamente colorido, por não conseguir pintar uma região respeitando a regra de evitar ambiguidades.
Como vimos acima, o mapa da Figura 3, com 4 cores, define um jogo que o Max ganha. Contudo, não é difícil concluir que o mesmo mapa, com n=5, representa um jogo que o Min vence se jogar bem.
Pois bem, podem desenhar mapas e atribuir valores a n, criando assim inúmeros jogos diferentes. Todos interessantes e divertidos!
Por exemplo, quem ganha jogando no seguinte mapa com n=5? E com n=6?
Fig. 6
A pergunta final, para preencher os serões de confinamento: qual é o menor valore de n que garante a vitória de Min, independentemente do mapa plano?
O autor poderá ser contactado através do e-mail jnsilva@cal.berkeley.edu