Re: Solucao do problema das pulgas

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sun, 6 Aug 2000, Marcio wrote:

> Leiam isso que eu escrevi sobre o problema das pulgas que apareceu na
> imo2000 e comentem..
> Nao aguento mais pensar nesse problema por enquanto :)
> Achei muito estranho o q eu mesmo escrevi nos ultimos 3 paragrafos.. leiam,
> e comentem/consertem :
> 
> (vou usar c ao inves de lambda pq nao sei escrever lambda em ascii).
> 
> Seja Di a distancia entre a pulga da extrema direita e o ponto M.
> Nosso objetivo é determinar os valores de l para os quais existe k tq Dk <
> 0. (pois isso significa que uma pulga esta a direita de M, e
> consequentemente com mais alguns movimentos todas as outras tmb estarao ja
> que l>0.).
> 
> Vou representar cada pulga por * e a distancia entre dois "*" consecutivos
> ou entre "*" e o ponto M esta indicada entre eles:
> 
> Primeiro, da pra mostrar, algebricamente, que a melhor opcao eh sempre a
> pulga mais da esquerda pular sobre a pulga mais a direita (os casos n=2,3
> sao faceis, e os outros eu imagino q sejam analogos).

Esta afirmação não me é muito clara; a melhor opção em que sentido?
Aceito que esta jogada é intuitivamente tão boa ou melhor do que qualquer
outra e no caso de desejarmos mostrar que para um dado valor de c
as pulgas sim ultrapassam qualquer marca podemos seguir esta estratégia.
Para a recíproca, i.e., para mostrar que para certo valor de c as pulgas
jamais poderão ultrapassar certo ponto, acho que falta um argumento
mais cuidadoso.
> 
> Analisando dessa maneira, vemos que (enqto a distancia for positiva), sua
> expressao eh dada pela recorrencia:
> 
> Di+n = Di+n-1 - c(Di - Di+n-1) cuja eq. caract. eh t^n = t^(n-1) - c(1 -
> t^n-1) = (1+c)t^n-1 - c.
> Dai, (t-1)t^(n-1) = c(t^n-1 - 1). Fatorando a raiz t=1 que corresponde a
> seq. constante temos:
> t^(n-1)=c(1+t+t^2+...+t^(n-2)).

Esta recorrência está ótima, mais elementar talvez do que a álgebra linear
que eu sugeri na minha solução.

> Em outras palavras, a solucao explicita de Dk eh da forma Dk = K + Ek para
> todo k, onde Ek satisfaz:
> Ek+n-1 = c(Ek + Ek+1 + ... + Ek+n-2) *.

Já esta fórmula eu absolutamente não entendi. Por mim teríamos
D_i = a_1 x_1^i + a_2 x_2^i + ... + a_n x_n^i
onde x_1, x_2, ..., x_n são as raízes do polinômio.
Tudo isto se o polinômio não tiver raízes duplas.
Dado isto, fica difícil comentar o resto da sua solução.
> 
> Agora, a seq. Dk eh claramente decrescente (note que ela soh faz sentido
> para todo n tal que Dt>0 se t<n):
> Temos entao os seguintes casos:
> (i) Se nao existir real L tq L=lim Dk, entao eh porque Dk tende pra menos
> infinito, o que significa que a em alguma hora será Dn<0 e pronto. (note que
> existe L se so se existe lim Ek)
> (ii)Se existir L=limDk : Se L>=0, é pq nunca se atingira o ponto M (lembre
> que Dn eh decrescente).
> (iii)Se for L<0, entao para algum n teremos Dn<0 e portanto as pulgas chegam
> a direita de M.
> 
> Bom, caso o limite exista, passando a eq. * ao limite vemos que deve ser:
> L' = c(L'+L'+...L') = cL'(n-1)
> portanto, caso o limite exista, ou vale L'=0 (L=K) ou entao c=1/(n-1)**.
> 
> O que fica faltando, eh achar uma relacao entre o fato de ser L>=0 e c <
> 1/(n-1).. (eu suponho que exista essa relacao por causa da resposta que eu
> li na msg do nicolau).
> O caso n=2 eh facil pq ai a sequencia Ek eh uma PG.. fico esperando ajuda
> para o caso n>2...

O valor de c afeta os valores das raízes e portanto afeta o comportamento
a longo prazo das pulgas. O essencial é saber se existem raízes de
módulo >= 1 além da raiz trivial 1.
> 
> Como Dk eh decrescente (pelo menos enqto Dk>0), entao Ek deveria ser
> decrescente tmb.
> Mas aih, o que temos eh:
> Ek+n-2 > Ek+n-1,  Ek+n-3 > Ek+n-1, ... Ek > Ek+n-1 e entao,
> (Ek+...+Ek+n-2) > (n-1)Ek+n-1 donde Ek+n-1 = c(Ek+...+Ek+n-2) >
> c(n-1)Ek+n-1.
> 
> Entao, se Ek+n-1 > 0 sempre precisa ser c < 1/(n-1) e reciprocamente.
> 
> Ou seja, para c>=1/(n-1) deve ser En<0 sempre..
> Nesse caso o limite de En nao pode ser nulo, e entao, como sabemos que L'
> caso exista vale zero, concluimos o limite L' vai para menos infinito.
> Entao, qq q seja a constante K (aquela para a qual Dt = K + Et), sempre
> existira um n suficientemente negativo para o qual Dn < 0.
> Ou seja, se c>=1/(n-1), entao eh possivel colocar uma das pulgas a direita
> de M. (E a partir dai eh soh ir pulando as demais sobre estas que obteremos
> todas as pulgas a direita de M).
> 
> Por outro lado, se c<1/(n-1) temos Ek+n-1 > 0 sempre, e portanto (Ek) eh
> limitada e decrescente. Existe portanto L'=limEk, que deve entao valer zero
> por **.
> O valor de K depende apenas dos valores iniciais de D1,D2,... . Eu suponho
> (aqui eu nao tenho total certeza) que qualquer valor de K pode ser obtido
> com uma configuracao inicial apropriada. Em particular, existiram
> configuracoes com K>=0.. e nesse caso teremos lim Dk = K >= 0 donde nenhuma
> pulga consegue chegar a direita de M num numero finito de passos.
> 
> Marcio
> 

[]s, N.