Ensino Médio ⇒ Combinatória Tópico resolvido

[Deleted User 23699]

Considere n retas num plano satisfazendo as seguintes condições:
1. Não existem duas retas paralelas
2. Não existem três retas concorrentes no mesmo ponto
Em quantas regiões fica dividido o plano pelas n retas?

Resposta

---

(n^2 + n + 2)/2

[MateusQqMD]

Encontrei alguns sites que discutem isso. Veja abaixo.

Fonte: https://www.cut-the-knot.org/proofs/Lin ... lane.shtml

Number of Regions N Lines Divide Plane 1.png (168.62 KiB) Exibido 920 vezes

Number of Regions N Lines Divide Plane 2.png (124.4 KiB) Exibido 920 vezes

[Deleted User 23699]

Resolução por PIF:
Definimos Xn o numero de partes em que o plano fica dividido ao traçarmos n retas de acordo com as condições dadas.

Vejamos casos iniciais:
N = 1 implica X1 = 2
N = 2 implica X2 = 4
N = 3 implica X3 = 7
N = 4 implica X4 = 11

Observe que
X1 = 1 + 1
X2 = 1 + 3
X3 = 1 + 6
X4 = 1 + 10

Perceba que o segundo termo é 1 somado à soma dos n primeiros inteiros positivos
Ex: X3 = 1 + ((((((6))))))
Sendo 6 = 1 + 2 + 3 (((((os 3 inteiros positivos)

Conjecturamos portanto que
Xn = 1 + ( 1 + 2 + 3 ... + n )
Aplicando soma de PA
Xn = 1 + (n (n+1))/2

Temos que provar nossa conjectura por indução finita
1. Casos iniciais: ja feitos!
2. Hipótese de indução: assuma que k retas dividem o plano em Xk = 1 + (k(k+1))/2 partes (conforme nossa conjectura).
3. Passo indutivo: temos que provar que K+1 retas dividem o plano em 1 + (K+1)(K+2)/2 partes.

Por hipotese, k retas dividem o plano em Xk = K(K+1)/ 2 partes.

Vamos traçar a reta de numero K + 1.
Ela deve intersectar todas as K retas que ja existiam no plano. Sobre ela irao surgir K pontos de intersecção novos.

O total de novos segmentos (ja considerando os extremos) é K+1. E cada segmento estara dividindo as regioes em volta deles em 2 partes.

Pense numa reta com diversos circulos de mesmo raio. Mais exatamente, K + 1 circulos. Essa é a ideia que estamos usando. Cada segmento seria um diametro, pertencente a circunferencia, de uma desses círculos. Esse diametro divide o circulo em duas partes. Essa é a ideia.

Portanto, o total de partes agora com K + 1 retas é

X(k+1) = Xk + (K+1)
Como temos Xk por hipotese
Basta substituirmos e reduzir a expressao

Iremos chegar a

X(k+1) = 1 + ((k+1)(k+2)/2)

Conforme era solicitado nesse problema de combinatoria do livro 3 do Rufino.

[Deleted User 23699]

Solução por interpolação de Lagrange, possivelmente o meio mais fácil de resolver uma questão desse tipo:

Por tentativa, vemos que
n = 1 implica 2
n = 2 implica 4
n = 3 implica 7
Temos 3 pontos (1,2) (2,4) e (3,7)
Basta fazer a interpolação de Lagrange
A fórmula obtida é exatamente a pedida

[Deleted User 23699]

Solução por relações de recorrência em combinatória:

Evidentemente, a situação em que temos um maior número de partes ocorre quando não existem duas retas paralelas, ou seja, todo par de retas é concorrente. Suponha que já temos traçadas, de acordo com as condições anteriores, n-1 retas no plano, dividindo este em x_(n-1) partes. Traçando mais uma reta que intercepte todas as n-1 já traçadas, podemos notar que entre quaisquer dois pontos de interseção consecutivos (contando os extremos) desta nova reta podemos associar uma nova parte do plano criada. Assim, podemos afirmar que
[tex3]x_n=x_{n-1}+n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x_n=x_{n-1}+n[/tex3]

onde x1 = 2
Assim:
[tex3]x_2=x_1+2 \\
x_3=x_2+3\\
...\\
x_n=x_{n-1}+n\\
\text{Somando tudo...}\\
x_n=x_1+(2+3+...+n)=2+\frac{(2+n)(n-1)}{2}=\frac{n^2+n+2}{2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x_2=x_1+2 \\
x_3=x_2+3\\
...\\
x_n=x_{n-1}+n\\
\text{Somando tudo...}\\
x_n=x_1+(2+3+...+n)=2+\frac{(2+n)(n-1)}{2}=\frac{n^2+n+2}{2}[/tex3]