Dispondo de
cores, de quantas formas esse mapa pode ser colorido de modo que países que façam fronteira tenham cores distintas?
Passo 1
O enunciado pede: de quantas maneiras, usando
cores, é possível colorir o mapa mostrado de modo que países que façam fronteira tenham cores distintas?
Informações dadas e observações visuais (retiradas da figura):
Informações dadas e observações visuais (retiradas da figura):
- Existem exatamente quatro países (quatro setores do círculo).
- As fronteiras são as duas diagonais (diâmetros) perpendiculares que dividem o círculo em quatro “quadrantes”.
- Cada país faz fronteira com os dois países adjacentes ao longo das divisórias (ou seja, cada país tem exatamente dois vizinhos).
- Dois países opostos (que ficam em quadrantes opostos) se tocam apenas no ponto central; portanto, não são considerados vizinhos (não há fronteira de comprimento positivo entre eles).
- Temos
cores disponíveis e queremos contar todas as colorações em que países vizinhos tenham cores diferentes.
Passo 2
Modelagem simples: representar cada país por um vértice e ligar por uma aresta dois vértices se os países correspondentes fazem fronteira. Pela observação do passo anterior, o grafo de adjacência é o ciclo com 4 vértices, chamado
(um quadrado em termos de grafo). Então a tarefa é contar o número de colorações próprias (proper colorings) de
com
cores, isto é, atribuições de cores aos vértices tal que vértices ligados por aresta tenham cores distintas.
Passo 3
Definição e estratégia de contagem:
- Uma coloração própria de
é uma função que associa a cada vértice uma das cores, com a restrição “vértices adjacentes têm cores diferentes”. - Vamos contar de forma construtiva, atribuindo cores em ordem ao longo do ciclo (vértice 1, 2, 3, 4) e fazendo um pequeno caso quando necessário.
Passo 4
Colorindo os três primeiros vértices em sequência:
- Para o vértice 1 (país 1) há
escolhas. - Para o vértice 2 (vizinhança de 1) há
escolhas (não pode usar a cor do vértice 1). - Para o vértice 3 (vizinhança de 2) devemos garantir apenas que sua cor seja diferente da do vértice 2; a relação com o vértice 1 ainda será tratada depois. Portanto, o número de escolhas para o vértice 3 depende se ele fica com a mesma cor do vértice 1 ou não — por isso fazemos caso 1 e caso 2.
Passo 5
Caso 1: o vértice 3 tem a mesma cor do vértice 1.
- Escolhas para vértice 1:
. - Escolhas para vértice 2:
. - Escolhas para vértice 3 (forçar igual a 1):
(já fixado). - Agora o vértice 4 deve ser diferente de ambos os vizinhos: é vizinho de 3 (que tem a mesma cor de 1) e de 1; mas como as cores de 1 e 3 são iguais, a restrição é apenas “não usar essa cor única”, logo há
escolhas para o vértice 4. - Total do caso 1:
.
Passo 6
Caso 2: o vértice 3 tem cor diferente da do vértice 1.
- Escolhas para vértice 1:
. - Escolhas para vértice 2:
. - Agora, para que o vértice 3 seja diferente de 2 e também diferente de 1, restam
opções (excluem-se as cores de 1 e de 2, que já são distintas). - O vértice 4 deve ser diferente de 3 e de 1; como as cores de 1 e 3 são diferentes neste caso, isso exclui duas cores, logo há
escolhas para o vértice 4. - Total do caso 2:
.
Passo 7
Somando os dois casos obtemos o total de colorações próprias de
:
Podemos simplificar essa expressão; uma forma elegante, conhecida para o ciclo
, dá para
a fórmula
As duas expressões são equivalentes (pode verificar expandindo e simplificando). Assim o número desejado de colorações é
.