Seção 3.1
Seja
o número máximo de regiões em que
retas podem dividiro plano. Caracterize
recursivamente.
Seja
Passo 1
O enunciado define
como o número máximo de regiões em que
retas podem dividir o plano e pede uma caracterização recursiva de
.
Informações dadas e o que se pede:
Informações dadas e o que se pede:
- Dado: para cada inteiro
, é o máximo de regiões obtidas com retas. - Pedido: encontrar uma relação recursiva que determine
a partir de valores anteriores (ou seja, expressar em função de ou de termos anteriores) e o caso inicial necessário.
Passo 2
Para maximizar o número de regiões, devemos colocar as retas em posição “geral”, isto é: nenhuma duas retas sejam paralelas e não haja três retas concorrendo num mesmo ponto. Explique por que isso importa: se houver retas paralelas ou três (ou mais) passando pelo mesmo ponto, elas criam menos interseções e, portanto, menos segmentos e menos regiões. Então, ao buscar o valor máximo
, assumimos que as
retas estão em posição geral.
Passo 3
Considere que já temos uma configuração ótima com
retas, que produz
regiões (isso é a hipótese recursiva). Agora adicionamos a
-ésima reta. Cada uma das
retas anteriores pode intersectar a nova reta em no máximo um ponto, e como não permitimos três retas concorrendo, essas interseções são todas distintas. Logo o número máximo de pontos de interseção da nova reta com as anteriores é
.
Passo 4
Esses
pontos de interseção dividem a nova reta em
pedaços (segmentos), porque um segmento aparece entre dois pontos consecutivos de interseção, e há ainda dois semi-intervalos infinitos nas pontas; em termos gerais, número de segmentos
número de interseções
. Ou seja, a nova reta fica dividida em exatamente
partes.
Passo 5
Cada um desses
segmentos corta uma região já existente em duas, aumentando o número total de regiões em
para cada segmento. Explicação geométrica simples: entre duas interseções consecutivas a porção da reta está inteiramente dentro de uma região única e a traça dessa porção divide essa região em duas. Não há sobreposição de efeitos porque assumimos posição geral (sem interseções múltiplas). Portanto, ao inserir a
-ésima reta, o número de regiões aumenta em
.
Passo 6
Da observação anterior segue a relação recursiva para
:
Precisamos também do caso inicial: com zero retas o plano fica inteiro, ou seja,
Como checagem rápida, para
obtemos
, que faz sentido (uma reta divide o plano em duas regiões).
Passo 7
Opcional: resolução fechada da recorrência (útil na prova). Somando a recorrência desde
até
obtemos
Usando a fórmula da soma dos primeiros
inteiros
(pode ser provada por emparelhamento ou indução), obtemos a forma fechada
Verificação para valores pequenos: para
temos respectivamente
, que batem com desenhos mentais ou casos conhecidos.