Re: Ajuda...

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Sauda,c~oes,

Retomo o problema das retas no plano.

-----Mensagem Original-----
De: Igor Castro
Para: OBM-Lista
Enviada em: Quinta-feira, 12 de Abril de 2001 00:13
Assunto: Ajuda...

Demonstrar por indução:
2º  n < 2^n
3º  Demonstrar que, traçando-se n retas em um plano, não se pode dividi-lo
em mais de 2^n "partes".

3o.) não estou me lembrando da recorrência. Acho que a RPM já tratou desse
problema. Alguém se habilita?

Achei o que estava procurando: na RPM 10, p. 45 vemos que: o número de
partes H_2(n) em que n retas em posição geral dividem o plano é:

H_2(n) = binom{n}{0} + binom{n}{1} + binom{n}{2}

Seja P(n) a proposição: H_2(n) <= 2^n.

Para n=1, temos 2 partes; para n=2, temos 4 partes e a proposição é
verdadeira. Devemos mostrar que H_2(k+1) <= 2^{k+1}.

Adicionemos ao conjunto {L_1, L_2,....L_k} a k+1-ésima reta, L_{k+1}; como o
conjunto  {L_1, L_2,....L_k} está em posição geral, vemos que cada uma das k
primeiras retas L_1,...L_k corta L_{k+1} em exatamente um ponto, e assim
L_{k+1} fica dividida em k+1 partes.

Observe, além disso, que cada uma das partes em que L_{k+1} está dividida
divide uma região (regiões velhas) do plano em duas, ou seja, cada parte de
L_{k+1} dá origem a mais uma região do plano; assim:

H_2(k+1) = H_2(k) + k+1 <= 2^k + k+1 < 2^k + k < 2^k + 2^k = 2^{k+1}.

Conclusão: H_2(n) < 2^n para n>= 3.

[ ]'s
Lu'is

-----Mensagem Original-----
De: Angelo Barone Netto <barone@ime.usp.br>
Para: <obm-l@mat.puc-rio.br>
Enviada em: Sábado, 14 de Abril de 2001 18:42
Assunto: Re: Ajuda...


3.
a) Cada reta nova so pode dividir em 2 as regioes velhas que atravessa.

b) 2 retas podem dlimitar 4 regioes.

c) a 3a. reta nao consegue atravessar as 4 (deixa o vertice em 1
semiplano, nao atravessa um dos angulos).

d) por a) o problema é imppossivel para n>3.

Angelo Barone{\ --\ }Netto                Universidade de Sao Paulo
Departamento de Matematica Aplicada       Instituto de Matematica e
Estatistica
Rua do Matao, 1010                        Butanta - Cidade Universitaria
Caixa Postal 66 281                       phone +55-11-3818-6162/6224/6136
05315-970 - Sao Paulo - SP                fax +55-11-3818-6131
Agencia Cidade de Sao Paulo
.