Re: [obm-l] Relacao de recorrencia

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Vamos por etapas:

Inicialmente, não é muito difícil ver que:
1 plano divide o espaço (R^3) em no máximo 2 regiões;
2 planos em no máximo 4 regiões;
3 planos em no máximo 8 regiões.

Assim, parece que cada novo plano dobra o número máximo de regiões. No
entanto, considere agora 4 planos.
Para facilitar a visualizaçao, suponha que os planos têm as seguintes
equações:

1. x = 0 (plano yz);
2. y = 0 (plano xz);
3. z = 0 (plano xy);
4. x + y + z = 1 (plano passando pelos pontos (1,0,0), (0,1,0) e (0,0,1) ).

Repare que estes 4 planos dividem R^3 no número máximo de regiões, uma vez
que 3 planos quaisquer se interceptam num único ponto.

O quarto plano só não intercepta o octante (x < 0, y < 0, z < 0) e divide
cada um dos outros 7 octantes em duas regiões.
Assim, estes quatro planos dividem o espaço em 8 + 7 = 15 regiões.

Pergunta: Por que o número de regiões não dobra com a adição do quarto
plano?
Resposta: Para que o número dobrasse, seria necessário que o quarto plano
interceptasse cada uma das 8 regiões determinadas pelos 3 primeiros planos
(os octantes, no nosso exemplo). Mas isso é impossível, uma vez que o ponto
de interseção daqueles três planos (a origem, no nosso exemplo) tem que
necessariamente estar situado em um dos dois semi-espaços determinados pelo
quarto plano. Assim, uma das regiões formadas pelos 3 primeiros planos (o
octante x < 0, y < 0, z < 0, no nosso exemplo) deixa de ser dividida pelo
quarto plano.

Adicione agora o quinto plano (em posição geral, ou seja, de modo que cada
três planos se interceptem num único ponto).

Os 4 primeiros planos se interceptam, três a três, em C(4,3) = 4 pontos
distintos. Cada um desses quatro pontos só pode estar num único semi-espaço
determinado pelo quinto plano. Assim, para cada um desses 4 pontos, uma
região formada pelos quatro primeiros planos deixa de ser dividida pelo
quinto plano, de forma que o número de regiões é igual a 2*15 - 4 = 26.

A relação de recorrência no caso geral é:
R(n) = 2*R(n-1) - C(n-1,3) = 2*R(n-1) - (n-1)*(n-2)*(n-3)/6, onde R(n) =
número máximo de regiões no espaço determinadas por n planos.

Com a condição inicial R(1) = 2, teremos:

R(n) = (n^3 + 5*n + 6)/6

Um abraço,
Claudio.




----- Original Message -----
From: <curupirazinho@bol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Sunday, January 19, 2003 2:09 PM
Subject: [obm-l] Relacao de recorrencia


Oi pra todos da lista,

     Eu estava resolvendo alguns exercicios sobre relacoes de recorrencia,
mas empaquei nesse:

    Dado um cubo apoiado num plano, apos passarmos 5 planos (seccionando o
cubo), qual o numero maximo de regioes no espaco determinadas por esses
cortes?

Obrigado antes de tudo,
Eduardo


__________________________________________________________________________
E-mail Premium BOL
Antivírus, anti-spam e até 100 MB de espaço. Assine já!
http://email.bol.com.br/


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================