On a giant tape measure sits an N-frog: that is, a frog with a special preference for the number N. The frog's location at the beginning of each of its jumps is called M. The frog moves on the tape measure according to the following rules:
Whenever M>N, then the N-frog makes an N-jump to the left and lands on the number M-N.
Whenever M<N, then the N-frog makes an N-jump to the right and lands on number M+N; during landing it also changes its preference and becomes an M-frog.
Whenever M=N then the frog is happy and stays on that number.
Where will a 851-frog that sits on 1517 be happy?
Where will an N-frog that sits on M be happy?
Let's call (M,N) the "state" of the whole thing, and M+N its "index".
Rule 1 says that you go from (P+Q,P) to (P,Q). Rule 2 says that you go
from (P,P+Q) to (2P+Q,P) -- and then, by rule 1, to (P+Q,P), and then
to (Q,P). Finally, rule 3 says that (P,P) is a final state.
We can prove the algorithm will end by noticing that the indices of
succesive states always is positive, and always goes down. (That isn't
actually true for the original rule 2, but we saw above that in three
steps you get from (P,P+Q) to (Q,P), so the index goes
down.)
Since the index is always a positive (M and N cannot get
to zero) decreasing number, it must eventually reach an stop, so that
implies the frog will be happy for all M and N.
Edited on July 10, 2005, 1:18 am
Why does it stop?
