The Linear Frog
I was given a problem recently, and I was really pleased to get the
solution. I wonder if you can (a) solve it, and (b) tell me where it
comes from. I've not been able to track it down at all.
|
I'm still gestating the post about
Puzzle World vs Crypto World. Not long now.
I hope. |
So here it is. I'm going to present it in two forms, to account for
the difference between Puzzle World and Crypto World.
The "Puzzle World" version ...
There's a set of lilypads stretching off beyond where the eye can see,
and we number them with the non-negative integers. So we label them,
starting with 0.
There's a frog who, one day, for no obvious reason, decides to hop on
the pads, starting somewhere random, and then hopping the same distance
each time, off into the distance. No, I have no idea why, but it seems
that it just wants to keep going.
But its plans were overheard by an unnamed predator. Our predator is
very, very short-sighted, and when close to one lilypad is unable to
see any others, but it's lightning fast. Sort of. So it decides to
visit lilypads, one at a time, in an attempt to catch the frog. There's
no limit to how far the predator can travel between lilypads, but it
needs to spend a unit of time at each one to detect whether or not the
frog is there.
So for every time step the predator moves to a lilypad, and the frog
jumps to the next in their sequence.
The question is:
- Can the predator catch the frog?
The "Crypto world" version
So here is the formulation in more precise and strictly mathematical
terms.
- Can you find a sequence $s(t)$ such that
for every arithmetic sequence $a+dt$ there
is a $t$ with $s(t)=a+dt$?
We are, of course, working in integers, and assume that $a$ and $d$
are non-negative.
Extension
Once you solve the problem for the frog moving in a linear pattern,
what if it moves in a Cubic? Or Quintic? Or Exponential? What if
$a$ and $d$ are allowed to be any integer (breaking the original idea
of the lilypads going off in one direction).
Problem source ...
So over to you. Firstly, can such a sequence be found? If so, what
is it, and if not, can you prove it?
Secondly, do you know a source for the problem? If so, let me know.
Enjoy!
Send us a comment ...
| 
Suggest a change ( <--
What does this mean?) /
Send me email
Subscribe!
