Let be a positive integer. A grasshopper stands on the number line at the number and may make either a jump of length or of length each time. Each time, the grasshopper must land on an integer from through where the grasshopper has not been before. The grasshopper would like to visit all integers from through exactly once and land on the number .
Prove that this can be done for all .
Solution
We distinguish different cases for based on the remainder of when dividing by .
If , then the grasshopper can jump as follows:
.
The grasshopper jumps over triples on the way out, over triples plus on the way back, and then over triples plus on the second way out.
If , then the grasshopper can jump as follows:
.
Finally, for , we find that the grasshopper can jump as follows:
.
Because we have that . In the solutions above for we see that every leg of the 'zigzag' is nonempty, so a solution exists.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.