Luiz precisa colorir os estados do mapa da região Norte do Brasil, mas esqueceu seu estojo de lápis de cor. Sabendo que ele não pode pintar estados que fazem fronteira entre si com a mesma cor, qual o número mínimo de lápis de cores diferentes que Luiz terá de emprestar de seus colegas?

Alternativa A

O problema apresentado é um clássico exemplo de coloração de mapas, que na matemática e na ciência da computação se relaciona com a Teoria dos Grafos e o famoso Teorema das Quatro Cores.

Este teorema afirma que qualquer mapa plano pode ser colorido usando no máximo quatro cores, de modo que regiões adjacentes nunca compartilhem a mesma cor. No entanto, para mapas específicos, muitas vezes menos cores são necessárias.

Análise Detalhada

Para resolver esta questão, devemos analisar as fronteiras dos estados da Região Norte mostrados no mapa para determinar o número mínimo de cores (lápises) necessários:

1. Identificação de Fronteiras Críticas:

• Observe os estados Pará, Amazonas e Rondônia. Eles formam um "triângulo" de fronteiras mútuas:
• Pará faz fronteira com Amazonas.
• Amazonas faz fronteira com Rondônia.
• Rondônia faz fronteira com Pará.
• Como esses três estados se tocam mutuamente, eles precisam obrigatoriamente de 3 cores diferentes entre si. Isso elimina a possibilidade de usar apenas 2 cores.

1. Verificação de necessidade de 4ª Cor:

• Para precisar de 4 cores, seria necessário encontrar um estado rodeado por 3 outros estados que, entre si, também fossem vizinhos (formando um "clique" de ordem 4).
• Analisando o restante do mapa:
• Roraima toca Pará e Amazonas (já coloridos).
• Amapá toca apenas Pará.
• Tocantins toca apenas Pará (no contexto restrito deste mapa).
• Acre toca Amazonas e Rondônia.
• Conseguimos distribuir as cores restantes sem conflitos usando apenas as 3 cores definidas inicialmente. Por exemplo:
• Pará: Cor 1
• Amazonas: Cor 2
• Rondônia: Cor 3
• Acre: Cor 1 (pois não toca o Pará)
• Roraima: Cor 3 (toca Pará e Amazonas, mas não Rondônia)
• Amapá: Cor 2 (toca apenas Pará)
• Tocantins: Cor 2 (toca apenas Pará)

1. Conclusão Lógica:

• Como verificamos que é possível colorir todo o mapa satisfazendo as regras utilizando apenas 3 cores, este é o número mínimo necessário.
• O enunciado informa que Luiz esqueceu o estojo, ou seja, ele possui 0 lápis. Portanto, o número de lápis que ele precisa emprestar é exatamente igual ao número de cores necessárias.

Portanto, o número mínimo de lápis de cores diferentes que Luiz terá de emprestar é 3.