Use a indução matemática para mostrar que quando n círculos dividem o plano em regiões, essas regiões podem ser coloridas com duas cores diferentes, tal que nenhuma região com margens comuns sejam coloridas com a mesma cor.

Passo 1

O enunciado pede para provar, por indução em n, que dada uma configuração de n círculos no plano, as regiões determinadas por esses círculos podem ser coloridas com duas cores (digamos, preta e branca) de modo que regiões que compartilham um arco de círculo não recebam a mesma cor. O conteúdo aqui é indução matemática e um argumento de “troca de cores” ao inserir o (n+1)-ésimo círculo.

Passo 2

Base da indução n=0: com zero círculos o plano inteiro é uma única região. Basta colorir essa região, por exemplo, de preta. Como não há adjacências, a condição é atendida.

Passo 3

Hiperótese de indução: suponha que para alguma n\ge0 toda configuração de n círculos admite uma 2-coloração das regiões com a propriedade desejada.

Passo 4

Passo indutivo: adicionamos um (n+1)-ésimo círculo à configuração de n círculos colorida segundo a hipótese. Esse círculo intersecta os anteriores em no máximo 2n pontos, dividindo-se em até 2n arcos, e cada arco passa por alguma região antiga, cortando-a em duas partes: uma parte “dentro” do novo círculo e outra “fora”.

Passo 5

Construção da nova coloração: mantenha as cores de todas as regiões que ficam fora (ou totalmente fora) do novo círculo. Para cada região que ficou cortada, pinte a parte que está dentro do novo círculo com a cor oposta àquela que ela tinha antes, e deixe a parte de fora com a cor original.

Passo 6

Verificação de que não surgem adjacências de mesma cor:
  1. Duas regiões que antes eram adjacentes por um arco de algum dos primeiros n círculos e continuam a compartilhar esse arco — esse arco fica totalmente fora do novo círculo ou totalmente dentro dele em cada ponto seu. Logo, ou ambas as regiões mantêm a cor antiga (se o arco ficou fora) ou ambas tiveram suas cores invertidas (se o arco ficou dentro), e em qualquer caso permanecem de cores diferentes por hipótese indutiva.
  2. Duas regiões que agora são adjacentes ao longo de um arco do (n+1)-ésimo círculo: uma está dentro e a outra está fora. Como as de dentro trocaram de cor e as de fora não, elas obrigatoriamente diferem de cor.

Passo 7

Concluímos que a nova coloração satisfaz a propriedade desejada para n+1 círculos. Isso completa o passo indutivo.

Resposta

Por indução, para todo n\ge0 as regiões formadas por n círculos no plano são 2-coloríveis de modo que regiões com margem comum têm cores diferentes.

Exercícios de Livros Relacionados