Um círculo foi dividido em
setores. De quantos modos podemos colori-los, cada setor com uma só cor, se dispomos de
cores diferentes e setores adjacentes não devem ter a mesma cor? -
Passo 1
O enunciado diz: um círculo foi dividido em
setores (
). Queremos colorir cada setor com exatamente uma cor, usando um conjunto de
cores diferentes (
), de modo que setores adjacentes tenham cores diferentes. A pergunta é: de quantos modos distintos podemos fazer essa coloração?
Informações relevantes que o enunciado dá:
- O número de setores é
. - O número de cores disponíveis é
. - Setores adjacentes não podem ter a mesma cor.
- Cada setor recebe exatamente uma cor.
- Devemos contar todas as colorações possíveis que satisfaçam a restrição.
Passo 2
Vamos numerar os setores ao redor do círculo como
no sentido horário. Assim, a restrição “adjacentes não têm a mesma cor” significa que, para cada
, a cor do setor
deve ser diferente da cor do setor
, com a convenção
(ou seja, o setor
também não pode ter a mesma cor que o setor
).
Uma técnica útil é “cortar” o círculo em algum ponto (por exemplo entre os setores
e
) e considerar primeiro o caminho linear de
a
(onde
e
já não são obrigatoriamente diferentes); depois impomos a condição adicional que a cor de
deve ser diferente da cor de
. Assim, contaremos colorings de um caminho e extrairemos dali as colorings válidas para o ciclo.
Passo 3
Para organizar a contagem, fixo a cor do setor
(isso facilita porque depois multiplicamos pelo número de escolhas para a cor de
). Seja
essa cor fixa. Para
considere os colorings do caminho de vértices
com a cor de
igual a
e que respeitam a restrição de adjacência entre vértices consecutivos. Defino:
-
= número de colorings do caminho (com cor de = ) tais que a cor do vértice é igual a . -
= número de colorings do caminho (com cor de = ) tais que a cor do vértice é diferente de .
Note que essas quantidades depend só de
e de
, não de qual cor específica
escolhemos, porque todas as cores são simétricas.
O número total de colorings do caminho
com cor de
fixa é
. Mas as colorings do ciclo correspondem apenas àquelas do caminho cujo vértice
tem cor diferente de
(pois no ciclo
e
são adjacentes). Assim, para uma cor fixa
teremos
colorings válidas; como há
escolhas possíveis para
, o total de colorings do ciclo será
. Logo nosso objetivo passa a ser determinar
.
Passo 4
Base inicial (casos pequenos), com cor de
fixa:
- Para
: só o vértice com cor . Então e . - Para
: o vértice deve ter cor diferente de , então há escolhas. Assim e .
Esses valores servirão para iniciar uma recorrência.
Passo 5
Vamos relacionar
e
com os termos anteriores, pensando em como construir colorings de tamanho
a partir de colorings de tamanho
.
- Para obter um coloring de tamanho
com o vértice igual a (contador ), o vértice obrigatoriamente deve ter cor diferente de . Portanto cada coloring contado em corresponde a um coloring de tamanho contado em , e a cor do -ésimo vértice fica determinada como . Logo
- Para obter um coloring de tamanho
com o vértice diferente de (contador ), existem duas possibilidades quanto à cor do vértice : - Se o vértice
tem cor (há colorings assim), então o vértice pode ser qualquer uma das cores diferentes de . Contribuição: . - Se o vértice
tem cor diferente de (há colorings assim), digamos que essa cor seja ; então o vértice não pode ser nem , ficando escolhas. Contribuição: .
- Se o vértice
Somando as duas contribuições:
Passo 6
Usando
(da relação acima aplicada com índice
), podemos eliminar
e obter uma recorrência apenas em
:
Reescrevendo:
com condições iniciais
e
.
Passo 7
Agora resolvemos essa recorrência linear homogênea de ordem 2 com coeficientes constantes. A equação característica é
Calculando o discriminante e as raízes:
logo as raízes são
Isso dá as duas raízes simples
Portanto a solução geral da recorrência tem a forma
onde
e
são constantes a determinar a partir das condições iniciais.
Passo 8
Usamos
e
para achar
e
.
Para
:
Para
:
Substituindo
:
Como
, podemos dividir por
e obter
, portanto
Assim
Passo 9
Lembrando que o número total de colorings do ciclo é
vezes
(pois multiplicamos pelas
escolhas para a cor do vértice
), obtemos:
Passo 10
Uma checagem rápida para ganhar confiança: se
(triângulo) e
cores, a fórmula dá
que é o número conhecido de colorings próprios do triângulo com 3 cores (equivalente a permutações de 3 cores na roda), então faz sentido.