[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] n circunferencias intersectantes (II)



 
Citando:
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
<>Um problema relacionado eh:

<>Qual o numero maximo de regioes em que o plano fica dividido por n
<>circunferencias?

<>n = 0 ==> 1 regiao (o plano inteiro)
<>n = 1 ==> 2 regioes (o interior e o exterior da circunferencia)
<>n = 2 ==> 4 regioes
<>n = 3 ==> 8 regioes

<>Tem cara de ser 2^n, mas serah que eh mesmo?

<>[]s,
<>Claudio.
 
""""""""""""""""""""""""""""""'"""""""""""""""""""""""""""""""""""""""""""""""""""""

      hmmmm....que tal generalizar a primeira pergunta para algo como:
      
      Qual o numero maximo de regioes em que o plano fica dividido por n
      L-agonos convexos?
     
      Seja x L-agonos dispostos em um plano,se desejando introduzir um novo.Quanto a isso, eu afirmo que no maximo 2*L*x novas regioes podem ser produzidas pela inserçao de um novo L-agono.Veja que cada lado do novo poligono introduzido intersecta no maximo 2*x lados         (2 lados de cada poligono) e que cada par de intersecçoes adjacentes SOBRE UM MESMO LADO determina uma regiao criada.Assim, cada lado introduzido cria no maximo 2*(x)-1 novas regioes.Sendo L lados a se introduzir(1 L-agono), o numero de regioes criadas pelos lados somam 2*L*(x)-L regioes.Tambem, existem L regioes criadas pelos  vertices do L-agono introduzido, que somadas as anteriores resultam em 2*L*x novas regioes, completando a demonstraçao de que 2*L*x é o maximo possivel de regioes a ser implementadas por um novo L-agono.
 
Chegaremos a f(n) usando um raciocinio indutivo: com 1 L-agono no plano no maximo 2*L regioes sao formadas pela inclusao de outro,
com 2 L-agonos no plano no maximo 2*L*2 regioes sao criadas, com 3 L-agonos no maximo 2*L*3 regioes sao criadas, ...........,com n L-agonos no maximo 2*L*n sao criadas pela inclusao de outro.
Assim, um limitante superior para f(n) é: 2 + 2*L*1 + 2*L*2 + 2*L*3 +.....
+......+ 2*L*(n-1) = 2 + L*(n-1)*n.
Para provar que 2 + L*(n-1)*n é de fato o valor maximo, precisamos mostrar que existe uma disposiçao geometrica de n L-agonos que produza 2 + L*(n-1)*n regioes no plano :  Centralize um L-agono, e produza todos os outros (n-1) L-agonos pela rotaçao do primeiro em torno de seu eixo,  de maneira que nao exista 2 L-agonos sobrepostos.Assim feito, teremos dividido o plano em 2 + L*(n-1)*n  que por ser tambem o limitante superior, comprova f(n) = 2*L(n-1)*n.
 
Qual o numero maximo de regioes em que o plano fica dividido por n
      L-agonos convexos?Respota: 2 + L*(n-1)*n regioes.
Obs: eu estou considerando a regiao ilimitada na contagem.
 
O problema levantado pelo Claudio se restringe ao caso L=1 (Circulos).
Entao ao invez do palpite 2^n , a resposta é 2 + (n-1)*n.
 
Pessoal desculpe a falta de clareza na mensagem mas acho que de para entender o escrevi...
 
                 Saldaçoes pro pessoal, 
                        Felipe Rangel
                
 


Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador agora!