(A) Problema de Gincana: Colorindo mapa

Clique no botão abaixo para visualizar o problema.

Problema


A figura abaixo mostra um mapa com 5 países.


Qual é a menor quantidade de cores que permite colorir esse mapa, sendo que países com uma fronteira comum não podem ter a mesma cor?

Solução


Considere as regiões denotadas por A, B, C, D e E, como abaixo.

  • Claramente não conseguimos colorir o mapa com apenas uma cor, pois países com uma fronteira comum não podem ter a mesma cor.
  • Vamos, então, tentar utilizar apenas duas cores para colorir o mapa. Neste caso, a região A é colorida com uma cor, digamos, amarelo, enquanto E recebe outra cor, digamos, rosa. Como D é adjacente a E, D não pode ser colorida de rosa. Tentando usar apenas duas cores, colorimos D de amarelo. Raciocinando de maneira análoga, colorimos C de rosa.
    Porém, chegamos a um impasse: B é adjacente a A, e não pode ser pintada de amarelo. Da mesma forma, B é adjacente a C, não podendo ser rosa.
  • Então, precisamos de uma terceira cor; digamos, azul.

Assim, a menor quantidade de cores para colorir o mapa nas condições enunciadas é 3.


Solução elaborada pelos Moderadores do Blog.

Participou da discussão o Clube Lapidando Vencedores Matemáticos.

Primeira Gincana de 2023 – Clubes de Matemática da OBMEP
Nível A – Questão Fácil

Link permanente para este artigo: http://clubes.obmep.org.br/blog/a-problema-de-gincana-colorindo-mapa/