Ensino MédioCombinatória Tópico resolvido

Problemas sobre assuntos estudados no Ensino Médio devem ser postados aqui. Se o problema for de Vestibular, poste-o no fórum Pré-Vestibular

Moderador: [ Moderadores TTB ]

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Nov 2019 08 15:19

Combinatória

Mensagem não lida por 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




Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2693
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 21-02-24
Localização: Fortaleza/CE
Nov 2019 08 19:34

Re: Combinatória

Mensagem não lida por 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
Number of Regions N Lines Divide Plane 1.png (168.62 KiB) Exibido 892 vezes
Number of Regions N Lines Divide Plane 2.png
Number of Regions N Lines Divide Plane 2.png (124.4 KiB) Exibido 892 vezes



"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Fev 2020 05 12:53

Re: Combinatória

Mensagem não lida por 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.



Movido de IME / ITA para Ensino Médio em Ter 11 Fev, 2020 13:17 por ALDRIN

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Set 2020 14 14:16

Re: Combinatória

Mensagem não lida por 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



Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Set 2020 22 14:34

Re: Combinatória

Mensagem não lida por 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] 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]




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Ensino Médio”