Use a indução matemática para mostrar que se você desenhar linhas no plano, precisará apenas de duas cores para colorir as regiões formadas, para que duas regiões que têm uma fronteira comum não apresentem a mesma cor.

Passo 1

O problema pede para mostrar, por indução matemática, que para qualquer número de retas desenhadas no plano é possível usar apenas duas cores para pintar as regiões formadas, de modo que duas regiões que compartilham uma fronteira comum nunca fiquem com a mesma cor. O conteúdo fundamental aqui é indução sobre o número de retas n.

Passo 2

Base da indução n=0: com zero retas, o plano inteiro é uma única região. Basta escolher duas cores (digamos “Branca” e “Preta”) e pintar essa única região de “Branca”. Não há fronteira entre duas regiões, logo a condição é satisfeita.

Passo 3

Passo indutivo – hipótese de indução: suponha que para qualquer configuração de n retas no plano existe uma coloração de duas cores que atende ao enunciado.

Passo 4

Passo indutivo – prova para n+1 retas:
  1. Retire uma das retas da configuração de n+1 retas. Sobram n retas, e pela hipótese de indução já existe uma coloração válida das regiões formadas.
  2. Reponha a reta removida. Ela corta algumas regiões (atravessando as outras retas) e divide cada região atingida em duas. Antes da inserção, cada uma dessas regiões tinha uma cor bem definida.
  3. Para garantir que regiões vizinhas ao longo da nova reta fiquem em cores diferentes, faça o seguinte truque: escolha um dos lados (um semiplano) da nova reta e inverta a cor de todas as regiões daquele lado, mantendo as cores originais do outro lado.
  • Qualquer par de regiões que antes eram adjacentes e continuem no mesmo semiplano continuam com cores diferentes, porque ambas foram invertidas (ou ambas permaneceram iguais).
  • Qualquer par de regiões que foi separado pela nova reta era, antes da inserção, uma única região com cor X; após a inversão em um semiplano, uma delas fica com X e a outra com a cor oposta. Logo elas também têm cores diferentes.

Resposta

Por indução, toda configuração de retas no plano admite uma coloração com apenas duas cores, de modo que regiões com fronteira comum tenham cores distintas.

Exercícios de Livros Relacionados