Dispondo de \lambda 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 \lambda 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):
  • 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 \lambda 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 C_4 (um quadrado em termos de grafo). Então a tarefa é contar o número de colorações próprias (proper colorings) de C_4 com \lambda 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 C_4 é uma função que associa a cada vértice uma das \lambda 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á \lambda escolhas.
  • Para o vértice 2 (vizinhança de 1) há \lambda-1 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: \lambda.
  • Escolhas para vértice 2: \lambda-1.
  • Escolhas para vértice 3 (forçar igual a 1): 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á \lambda-1 escolhas para o vértice 4.
  • Total do caso 1: \lambda\cdot(\lambda-1)\cdot 1\cdot(\lambda-1)=\lambda(\lambda-1)^2.

Passo 6

Caso 2: o vértice 3 tem cor diferente da do vértice 1.
  • Escolhas para vértice 1: \lambda.
  • Escolhas para vértice 2: \lambda-1.
  • Agora, para que o vértice 3 seja diferente de 2 e também diferente de 1, restam \lambda-2 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á \lambda-2 escolhas para o vértice 4.
  • Total do caso 2: \lambda\cdot(\lambda-1)\cdot(\lambda-2)\cdot(\lambda-2)=\lambda(\lambda-1)(\lambda-2)^2.

Passo 7

Somando os dois casos obtemos o total de colorações próprias de C_4:
\lambda(\lambda-1)^2+\lambda(\lambda-1)(\lambda-2)^2=\lambda(\lambda-1)\Big[(\lambda-1)+(\lambda-2)^2\Big].
Podemos simplificar essa expressão; uma forma elegante, conhecida para o ciclo C_n, dá para n=4 a fórmula
(\lambda-1)^4+(\lambda-1).
As duas expressões são equivalentes (pode verificar expandindo e simplificando). Assim o número desejado de colorações é (\lambda-1)^4+(\lambda-1).

Resposta

(\lambda-1)^4+(\lambda-1)

Exercícios relacionados