Use a indução matemática para mostrar que quando
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
, que dada uma configuração de
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
-ésimo círculo.
Passo 2
Base da indução
: 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
toda configuração de
círculos admite uma 2-coloração das regiões com a propriedade desejada.
Passo 4
Passo indutivo: adicionamos um
-ésimo círculo à configuração de
círculos colorida segundo a hipótese. Esse círculo intersecta os anteriores em no máximo
pontos, dividindo-se em até
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:
- Duas regiões que antes eram adjacentes por um arco de algum dos primeiros
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. - Duas regiões que agora são adjacentes ao longo de um arco do
-é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
círculos. Isso completa o passo indutivo.
Resposta
Por indução, para todo
as regiões formadas por
círculos no plano são 2-coloríveis de modo que regiões com margem comum têm cores diferentes.