Disponho de 4 cores (V, A, M, P) para colorir o mapa da figura abaixo, contendo os países "X", " Y", "W", "Z", de modo que países cuja fronteira é uma linha não podem ser coloridos

Gabarito

D

Comentário do professor

Escolhemos primeiro a cor de X: há \(4\) opções.

Caso 1 — as cores de Y e W coincidem (mas diferem de X): para Y/W existem \(3\) escolhas; então Z, adjacente a Y e W, não pode usar essa cor, restando \(3\) opções. Total deste caso: \(4\times 3\times 3=36\).

Caso 2 — as cores de Y e W são distintas (ambas diferentes de X): após X (\(4\)) e Y (\(3\)), W tem \(2\) opções; Z não pode usar as cores de Y nem de W, sobrando \(2\) opções. Total: \(4\times 3\times 2\times 2=48\).

Soma dos casos: \(36+48=84\). Alternativamente, usando a fórmula para colorações próprias do ciclo \(C_4\) com \(k=4\): \((k-1)^4+(k-1)=3^4+3=84\).