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?

 

MapDescription automatically generated

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.

 

Shape, polygonDescription automatically generated

Fig. 2

 

Neste contexto, queria propor um jogo em que pode participar toda a família.

 

Consideremos a figura

 

A black rectangle with a black backgroundDescription automatically generated with low confidence

Fig. 3

 

De acordo com o T4C, podemos colori-lo com quatro cores, o que ilustramos abaixo.

 

A picture containing text, clockDescription automatically generated

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.

 

A picture containing text, clock, clipartDescription automatically generated

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?

 

Chart, radar chartDescription automatically generated

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
Publicado/editado: 04/02/2021