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?
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.
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
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]
Em uma festa, sabe-se que cada pessoa tem três amigos, mas que não há três pessoas que sejam amigas duas a duas. Qual é, então, a menor quantidade possível de pessoas na festa?
A) 9
B) 8
C) 7
D) 6
E)...
Última msg
Tive um raciocínio objetivo... se em um grupo de três pessoas não existe a amizade duas a duas, ou seja, quando ha tres pessoas, como João Pedro e Lucas, se tomarmos os amigos de Lucas, Pedro e João...
100 pessoas são convidadas para fazer parte de um jogo. Suponha que existem 12 objetos (com massas distintas) divididos em 4 grupos, cada um com três objetos. O participante escolhe 4 objetos, um de...
Um grupo constituído de 10 pessoas resolveu comemorar em uma chácara a conclusão de um curso que acabara de se encerrar. Para isso, o grupo viajaria em carros com a seguinte disponibilidade de...