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