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>
=========================================================================