Number of points that can be reached by following a certain pattern of jumps

Question

A frog begins at $P_0 = (0,0)$ and makes a sequence of jumps according to the following rule: from $P_n = (x_n, y_n),$ the frog jumps to $P_{n+1},$ which may be any of the points $(x_n + 7, y_n + 2),$ $(x_n + 2, y_n + 7),$ $(x_n - 5, y_n - 10),$ or $(x_n - 10, y_n - 5).$ There are $M$ points $(x, y)$ with $|x| + |y| \le 100$ that can be reached by a sequence of such jumps. I need to find the number of such points that can be reached. The only conclusion I have been able to draw is that whatever the point the frog jumps the sum of its coordinates is a multiple of 3 and difference of its coordinates is a multiple of 5, but I am unable to deduce the number of such points

Answer 1

1) Proof that the frog can move to any integer grid point $(x,y)$ that fullfills the conditions (as noted by the original poster) $x+y \equiv 0\pmod 3$ and $x-y \equiv 0 \pmod 5$:

First, I'll denote the jumps with $(+7,+2), (-10,-5)$ a.s.o.

Second, note that because each jump just adds a given number to each coordinate, the order jumps are made does not matter for the final end point. If the frog makes 2 jumps $(+7,+2)$ and then one jump $(-10,-5)$, the frog ends up in the same position as if he started with the $(-10,-5)$ and made the 2 jumps $(+7,+2)$ afterwards, or had the $(-10,-5)$ as the middle jump. One can write this as

$$2\times(+7,+2)+(-10,-5) = (+4,-1).$$

Note that $$5\times(+7,+2)+5\times(+2,+7)+3\times(-10,-5)+3\times(-5,-10)=(0,0)$$ This involves all 4 legal jumps, and this means that all legal jumps are reversible, because, from the above easily follows e.g. $$(-7,-2) = {\mathbf 4}\times(+7,+2)+5\times(+2,+7)+3\times(-10,-5)+3\times(-5,-10)$$ and the same for all the other reverses of the legal jumps. That means we can treat $(-7,-2)$ a.s.o. also as legal jumps.

Now lets take any $(x,y)$ that fullfills $x+y \equiv 0\pmod 3$ and $x-y \equiv 0 \pmod 5$. Because $\gcd(7,2)=1$ we can find integers $a,b$ with $7a+2b=x$.

Starting from $(0,0)$ we do $a$ jumps of the form $(+7,+2)$, if $a>0$, or $-a$ jumps of the form $(-7,-2)$ if $a<0$. If $a=0$ we do no jumps of that form. No matter what, we are now at a point with $x$-coordinate $7a$. Afterwards, we do $b$ jumps of the form $(+2,+7)$ (or $-b$ of the form $(-2,-7)$, or none, as appropriate).

That brings the frog to a point $(x,y_0)$ (remember $x=7a+2b$). With a given $x$, the reminder of $y$ after division by 3 is now uniquely determined by $x+y \equiv 0\pmod 3$, and the reminder after division by 5 is uniquely determined by $x-y \equiv 0 \pmod 5$. That means $y$ is uniquely determined $\pmod {15}$.

Since $y_0$ is also a possible $y$, we now know that $y \equiv y_0 \pmod {15}$.

Now we have

$$(+0,+15) = 2\times(+5, +10) + (-10,-5)$$

and the reverse

$$(-0,-15) = 2\times(-5, -10) + (+10,+5).$$

That means no matter if $y > y_0$ or $y < y_0$, we can reach $(x,y)$ from $(x,y_0)$ by applying a series of jumps in groups of 3 that moves the frog up or down by 15 units.

2) Counting the number of interger grid points with $x+y \equiv 0\pmod 3$ and $x-y \equiv 0 \pmod 5$ that are in the area described by $|x|+|y| \le 100$:

That area is a square with vertices $(-100,0), (0,-100),(100,0)$ and $(0,100)$. One convinient way (for this problem) is to divide it into 101 line segments $$(100,0) - (0,100),$$ $$(99,-1) - (-1,99),$$ $$(98,-2) - (-2,98),$$ $$\ldots$$ $$(50,-50) - (-50,50),$$ $$\ldots$$ $$(0,-100) - (-100,0).$$

Each line segment has a constant $x+y$ value (starting from $100$ in the first line, then $98$ to $-100$ in the last line. If that $x+y$ value is not divisible by $3$, then there are obviously no reachable points on that line segment for the frog.

If that $x+y$ value is divisible by $3$, then there are reachable points. It is easy to sea that if $(x,y)$ is such a reachable point, then the next ones (left or right of it) will be $(x-5,y+5)$ and $(x+5,y-5)$, that means every fifth point on that line segment will be a reachable point. Since each line segment contains 101 points, the number of reachable points on each line segment can be 21, if the first (and hence also the last) point of the line segment are reachable, or 20, otherwise.

If we use my above listing of the line segments, the first to have reachable points is

$$(98,-2) - (-2,98),$$ then come $$(95,-5) - (-5,94),$$ $$(92,-8) - (-8,92),$$ $$\ldots$$ $$(2,-98) - (-98,2),$$

alltogther 33 line segments. It's easy to see that the first point $(x,y)$ of all of these line segments satisfies $x-y=100$, so all 33 of those line segments contain 21 reachable points, for a grand total of $33\times 21=693$ reachable points.