Problemópolis é um lugar curioso. Além de reis enófilos cruéis, mesas de bilhar enigmáticas e funcionários públicos, há um lago infinito em todas as direções, com pedras uniformemente espaçadas num arranjo quadriculado infinito. Isto é: Problemópolis tem um lago isomorfo ao plano 
Um sapo está sentado na pedra (0,0), e a cada segundo pula para uma pedra diretamente ao leste ou ao norte. Isto é, se o sapo está na pedra (m,n), no segundo seguinte ele estará na pedra (m+1,n) ou (m,n+1).
Joãozinho observa o sapo por algum tempo e nota que, em certo momento, o sapo já visitou três pedras colineares. Observa mais um pouco, e nota que o sapo visitou quatro pedras colineares (não necessariamente incluindo as três primeiras). Joãozinho então se pergunta: será que, se eu olhar por bastante tempo, o sapo visitará k pedras colineares, qualquer que seja k?
André
javendo
aaronalb
Pietro
ynotx
Luís Guilherme Fernandes Pereira
mariogen
abgrilo
Antes de tudo um pouco de notação!
Seja p(n)=(x(n),y(n)) a posição do sapo após n movimentos assim temos: p(0)=(x(0),y(0))=(0,0). Temos também por exemplo: x(n)+y(n)=n.
Primeiro pensei se tratar de um problema de probabilidade. Já tinha até resolvido… hehehe
Mas quando fui procurar no problema o termo “com a mesma probabilidade…” não achei! De fato parece ser um problema de combinatória. ah se eu tivesse visto a tag…
O problema pode ser encarado então da seguinte maneira: o sapo tenta andar para a direita e para cima fugindo de passar por números arbitrariamente grandes de casas colineares. Ele consiguirá?
Vou fazer uma análise supondo que ele consiga (Eu acredito que não, de forma que espero chegar num absurdo!).
Se ele conseguir, no seu movimento ele só cruza a reta y=x um número finito de vezes, se mantendo depois de um certo tempo ou de um lado ou do outro dessa reta. A mesma coisa para qualquer outra reta da forma y = Ax, com ‘A’ real positivo: Para cada uma dessas retas existe um número de movimentos depois do qual o sapo se mantém apenas de um lado dessa reta, pois se ele a cruzasse infinitas vezes haveria um número infinito de pontos colineares no seu movimento.
Seja  o maior A tal que o sapo se mantém acima da reta y = Ax depois de algum tempo. O movimento do sapo tende para essa reta no seguinte sentido: por menor que seja E > 0, depois de um certo número de movimentos o sapo se mantem entre as retas y=Âx e y=(Â+E)x. Isso implica que lim y(n)/x(n) = Â, quando n tende ao infinto.
Parei meu raciocínio por aí. Será que sabendo y(n)/x(n) converge dá para concluir que existe um número arbitrariamente grande de ns para os quais y(n)/x(n) assume o mesmo valor? Ainda estou tentando resolver…
Mário, sua idéia é sensacional.
A única coisa que me preocupa é que estamos procurando *pontos* colineares no trajeto do sapo, e os passos dele são discretos. Em outras palavras, ele pode cruzar muitas vezes uma mesma reta “contínua” (os pontos em R² que satisfazem y=Ax) sem bater nos pontos inteiros desta reta. Por exemplo, o primeiro ponto inteiro da reta 97y = 101x, depois da origem, é (97,101); os outros são similarmente espaçados. O sapo poderia “trocar de lado” dessa reta várias vezes sem bater nos pontos inteiros dela.
De fato, há exemplos de passeio do sapo em que ele troca de lado dessa reta infinitas vezes sem passar por pontos colineares nela. (Talvez ele passe por outros pontos colineares.)
Pois é, no meu comentário anterior ainda não tinha muito bem na cabeça o que seriam essas “retas discretas”, mas deu pra formalizar essa questão sem perder o resultado a que já tinha chegado.
traçando o segmento que une (0,0) e (97,101) temos que os únicos pontos d0 segmento que tem coordenadas inteiras são os seus extremos. Como poderíamos tornar esse segmento mais denso nos pontos de coordenada inteira? Podemos adicionar os pontos P de coordenadas inteiras do plano tais que o segmento que une (0,0) e (97,101) intersecta o quadrado de centro no ponto P, de lados medindo 1 e paralelos aos eixos. Depois de adicionados esses pontos ao segmento, ele se torna denso e se o sapo quiser passar de um lado para outro do segmento ele terá que passar por algum ponto desse segmento.
Suponhamos que esse segmento tenha agora N pontos, digamos P1,P2,…,PN. O conjunto de pontos {Pi+k*(97,101), onde i,k são naturais e i varia de 1 a N} é o que passo a chamar de uma discretização da reta y=Ax. Se o sapo ultrapasse a reta y=Ax infinitas vezes, ele passaria por infinitos pontos da discretização dessa reta. Daí concluímos que haveria um i para o qual haveriam infinitos ks tais que o sapo passou pelos pontos Pi+k*(97,101), que são todos pontos colineares! Assim se o sapo pretende não passar por números arbitrariamente grandes de pontos colineares ele deve se manter, depois de um certo tempo, apenas de um lado da reta 97y=101x.
Da mesma forma que foi mostrado para o número 101/97, pode-se mostrar que o sapo deve se manter do mesmo lado da reta y=Ax depois de certo número de movimentos, qualquer que seja A racional! Isso já é suficiente para provar que se o sapo não passa por números arbirtrariamente grandes de casas colineares, existe um  = lim y(n)/x(n), quando n vai para o infinito.
Uma coisa que não compromete o resultado acima porém me deixou incucado é que não consegui provar que o sapo não cruza infinitas vezes a reta y=Ax, com A irracional. Definido a discretização da reta y=Ax, com A irracional, como sendo o conjunto dos pontos P tais que a reta intersecta o quadrado unitário de centro em P. Me pergunto se a discretização de uma reta com coeficiente angular irracional não é um contra exemplo para o problema…
Tres observaciones menores, ya que el problema está esencialmente resuelto por los argumentos anteriores:
1. Confio en la discretización de las rectas de pendiente racional. En el peor caso discretizaríamos por bloques cuadrados. Ejemplo, en la recta 97.Y=101.X, agregamos como primer bloque aquellos (x,y) con x<=97 e y<=101, y como sucesivos bloques las traslaciones por: k.(97,101). El sapo queda a un costado de tal discretización o cae infinitas veces en uno de estos cuadrados (pegando infinitas veces en algún casillero particular, lo cual da una sucesion colinear).
2. Basta pensar rectas de pendiente racional, siendo valores densos entre las posibles pendientes.
3. Un tecnicismo. El supremo en los valores de las pendientes al que hacen referencia como ´Â´ podria ser el infinito. En ese caso se prueba que el sapo da consecutivos saltos hacia el norte de longitud arbitraria.