Agora vou contar só as regiões limitadas. Para
isso, vou começar contando as ilimitadas.
Vamos imaginar que já desenhamos n retas. Agora
vamos desenhar um círculo bem grande, de modo que todas as interseções de retas
estejam dentro do círculo. Todas as regiões ilimitadas
intersectam o círculo. E só as regiões ilimitadas
intersectam o círculo. Então, para contá-las, basta contar quantas regiões
intersectam o círculo.
Vamos desenhar um ponto vermelho no círculo, sem
ele estar sobre nenhuma reta. Agora vamos passar um filme do ponto andando
pelo cículo, até dar uma volta. Ele começa em alguma região. Daí, quando bate em
uma reta, pula para outra região. E assim continua, até que ele bate em uma reta
pela última vez e volta para a primeira região. Então o número de regiões é o
número de vezes que ele bate nas retas. Como ele bate duas vezes em cada reta,
são 2n regiões ilimitadas.
Como já tinhamos contado o número total de regiões
R(n), o número máximo de regiões limitadas é R(n) menos as 2n regiões limitadas.
Vamos chamar esse cara de L(n):
L(n) = R(n) - 2n = n(n+1)/2 + 1 - 2n = n(n-3)/2 +
1
Agora vamos desenhar alguns casos para testar a
fórmula:
L(0)=0
L(1)=0
L(2)=0
L(3)=1
L(4)=3
Êpa!!! A fórmula deu errado pra n=0! Bem, isso era
de se esperar, já que o argumento acima é totalmente furado quando não tem
nenhuma reta. Mas ela deu certo para todos os outros valores, então parece que
vale para n>0.
Agora aos números. L(58)=1596 e L(59)=1653. Mas
esse é o número máximo de regiões que pode ser atingido. Se algumas retas forem
paralelas, o número de regiões é menor.
Mas será que dá pra consegui 1597 com 59 retas?
Dá!
Se duas forem paralelas, o número de regiões
diminui por um. Se três forem paralelas, o número de regiões diminui por 3.
Então basta desenhar 59 retas, sendo 54 paralelas três a três e 4
paralelas duas a duas.
- Original Message -
From:
Eduardo Azevedo
To: [EMAIL PROTECTED]
Sent: Wednesday, August 06, 2003 7:49
PM
Subject: Re: [obm-l] Problemas em aberto
1
Esse é clássico. Estou surpreso que ninguém
respondeu até agora. Só não entendi o que é :(A area externa aos vertices das extremidades nao entra na
contagem).
Imagino que seja pra contar só as regiões
limitadas? Bom, vou fazer contando todas (que o 1597 indica ser a
interpretação correta do problema), que, depois que você explicar
melhor,
deve dar pra ajustar as contas.
Vou chamar de R(n) o número máximo de regiões em
que o plano plano pode ser dividido por n retas. Isso contando as regiões "de
fora", aquelas que são ilimitadas.
Claramente
R(0)=1
R(1)=2
R(2)=4 (faço um X com as retas)
R(3)=7 (desenho a 3a não paralela as 2
primeiras)
Agora vou tentar achar uma relação entre R(n) e
R(n-1). Para isso vamos imaginar um filme da 3a reta sendo
desenhada.
Antes dela encostar nas outras duas só há R(2)=4
regiões.
Quando ela bate na 1a reta surge mais
uma.
Quando bate na segunda surge outra.
Quando ela chega no infinito (no final do filme)
aparece mais outra.
Hummm. Parece que R(n) é R(n), mais (n -1)
regiões que aparecem quando a reta nova bate nas (n - 1) outras
retas(é só desenha-la paralela as anteriores), mais 1 quando ela bate no
infinito. Ou seja,
R(n)= n+R(n-1) = n+ (n-1) +R(n-2) = = n +
(n-1) + (n-2) + ... + 1 + R(0) = n(n+1)/2 + 1
Felizmente isso bate com os valores que a gente
calculou antes. Ufa!
Agora, você pediu o menor n tal que
R(n)= n(n+1)/2 + 1 é pelo menos 1597. Resolvendo
a eq. do 2o grau, R(56)=1597, na
mosca!
