Problem:
A frog begins at P0=(0,0) and makes a sequence of jumps according to the following rule: from Pn=(xn,yn), the frog jumps to Pn+1, which may be any of the points (xn+7,yn+2),(xn+2,yn+7),(xn−5,yn−10), or (xn−10,yn−5). There are M points (x,y) with ∣x∣+∣y∣≤100 that can be reached by a sequence of such jumps. Find the remainder when M is divided by 1000.
Solution:
Note that xn+1+yn+1=xn+yn(mod3) and xn+1−yn+1=xn−yn (mod5), so each reachable point is at the intersection of a line x+y=3j and a line x−y=5k with −33≤j≤33 and −20≤k≤20. Furthermore, j and k must have the same parity. The number of points that meet these conditions is 33⋅21+34⋅20=1373. Call these points good.
To see that each good point is reachable, note first that it is possible to move from the line x−y=5k to either of the lines x−y=5(k+1) or x−y=5(k−1) by moving from (x,x−5k) to (x−5,x−5k−10) or (x+2,x−5k+7), respectively. Therefore there is at least one reachable point on each line x−y=5k for −20≤k≤20. It is also possible to go from (x,y) to either (x+9,y+9) or (x−15,y−15) in two moves, so it is possible to make a sequence of moves from (x,x+5k) to either (x+3,x+5k+3) or (x−3,x+5k−3). Thus if any good point on the line x−y=5k is reachable, so is every good point on that line. This implies that M=1373, and the remainder when M is divided by 1000 is 373.
The problems on this page are the property of the MAA's American Mathematics Competitions