Solucao do problema das pulgas

["Marcio" <mcohen@xxxxxxxxxx>]

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

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

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

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