RES: Solucao do problema das pulgas

["Marcio" <mcohen@xxxxxxxxxx>]

-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
nome de Nicolau C. Saldanha
Enviada em: Segunda-feira, 7 de Agosto de 2000 14:15
Para: obm-l@mat.puc-rio.br
Assunto: Re: Solucao do problema das pulgas




On Sun, 6 Aug 2000, Marcio wrote:

> (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.).
>
> 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.

O que eu tinha em mente era isso:
Temos que toda sequencia satisfazendo * satisfaz tambem a recorrencia em Dk.
Pois (Ek) satisfaz * =>Ek+n-1 = c(Ek + Ek+1 + ... + Ek+n-2) e Ek+n=c(Ek+1 +
Ek+2 + ... + Ek+n-2 + Ek+n-1).
Logo, Ek+n = Ek+n-1 + cEk+n-1 - cEk donde (Ek) satisfaz a recorrencia Di+n =
Di+n-1 - c(Di - Di+n-1).
Agora, 1 nao eh raiz da eq. caract. de (Ek), e portanto sua solucao geral eh
da forma
Ek = a_1 x_1^i + a_2 x_2^i + ... + a_n-1 x_n-1^i.
Essas raizes x_i sao tambem raizes da eq. caracteristica em (Dk) (pela
fatoracao feita la em cima). Como a outra raiz dessa equacao eh x_n=1, temos
Dk=K + a'_1 x_1^i + a'_2 x_2^i + ... + a'_n-1 x_n-1^i
Portanto, toda solucao particular de (Dk) eh da forma Dk = K + Ek, onde Ek
eh uma solucao de Ek+n-1 = c(Ek + Ek+1 + ... + Ek+n-2). Acho que o problema
foi que era para diferencia K (maiusculo) de k(minusculo). K eh uma
constante real qualquer, e k eh o subindice.

Quanto a outra observacao que vc fez la em cima, eu ainda estou tentando ver
se consigo provar que fazer sempre a pulga da extrema esquerda pular sobre a
da extrema direita eh a melhor maneira de minimizar Dk a longo prazo.. (se
eh que isso eh realmente verdade. aceito ajuda :) ).



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

Marcio