Let $a > b$ be relatively prime positive integers. A grashopper stands at point $0$ in a number line. Each minute, the grashopper jumps according to the following rules: If the current minute is a multiple of $a$ and not a multiple of $b$, it jumps $a$ units forward. If the current minute is a multiple of $b$ and not a multiple of $a$, it jumps $b$ units backward. If the current minute is both a multiple of $b$ and a multiple of $a$, it jumps $a - b$ units forward. If the current minute is neither a multiple of $a$ nor a multiple of $b$, it doesn't move. Find all positions on the number line that the grasshopper will eventually reach.
Problem
Source: Mexico National Olympaid 2019 P5
Tags: number theory, algebra
62861
13.11.2019 04:44
The answer is the interval of integers $I \stackrel{\text{def}}{=} [-(a-1), +(b-1)]$.
Claim. The grasshopper never leaves the interval $I$.
Proof. Let's prove that it never takes on a value $\ge b$ (similar proof for $\le -a$). After the $t^{\text{th}}$ minute, it moves $+a$ $\lfloor \tfrac{t}{a} \rfloor$ times and $-b$ $\lfloor \tfrac{t}{b} \rfloor$ times, so the net displacement is
\[a \left\lfloor \frac{t}{a} \right\rfloor - b \left\lfloor \frac{t}{b} \right\rfloor < a \cdot \frac{t}{a} - b \left(\frac{t}{b} - 1\right) = b,\]as desired.
Now observe that for any integer $n \in I$, exactly one of $n+a \in I$ and $n-b \in I$, except for $n = b-a$ for which neither is in $I$. In addition, observe that during a multiple of $ab$ minutes, the grasshopper goes $b-a \mapsto 0$. Thus, the sequence of grasshopper positions is a simple $(a+b-1)$-periodic recursion starting at 0, with each element depending only on the previous one.
We claim that its least period is $a+b-1$, which solves the problem (then the recursion has $a+b-1$ has different elements, and so contains all of the integers in $I$). To see this, suppose an element $n \in I$ appears twice; then between these two occurrences, the grasshopper has a net displacement of 0. Since it can only make $+a$ and $-b$ moves (interpret the $a-b$ move as both applied together as one move), it must have made at least $a+b-1$ moves, as desired.
idkwhatthisis
13.11.2019 11:15
Claim: The set of all the points the grasshopper visits is $\{1-a,...,b-1\}$.
Lemma: At time $ab$ minutes, the grasshopper stands at point 0.
Proof: There are $b-1$ multiples of $a$ below $ab$, and $a-1$ multiples of $b$ below $ab$, and all at all other times stands still. So at time $ab$, it is on point $-b(a-1)+a(b-1)+(a-b) = 0$. Hence this claim has been proved.
Since the set of positions the grasshopper can visit is periodic with period $ab$ minutes, we just need to consider the positions the grasshopper travels from in the interval $[0,ab)$.
Lemma 2: Each point the grasshopper visits is different.
Proof: Considering the positions of the grasshopper when the time is between 2 multiples of $a$, the positions have constant remainder $\mod b$. Since $\gcd(a,b) = 1$, the positions of the grasshoppers in the time intervals $[0,a), [a,2a-1), ... [a(b-1),ab)$ are congruent to $0,a,...,(b-1)a \mod b$ respectively, which is the complete system of residues$\mod b$ , thus once it never repeats positions.
Let $a = kb+c$, where $0<c<b$ and $\gcd(c,b)=1$. If $xa \equiv b-1,b-2,...,b-c$, there are $k+1$ multiples of b between $xa$ and $(x+1)b$, and when $xa \equiv 0,1,...,b-c-1$, there are $k$ multiples of b between $xa$ and $(x+1)b$.
We will now prove that when the grasshopper is in a position in the interval $[0,b-1]$, after it moves backwards $b$ steps and then moves forwards $a$ steps, it will still be in the interval $[0,b-1]$.
Case 1: $y \equiv xa \equiv 0,1,...,b-c-1$
The grasshopper moves $b$ places backwards $k$ times, thus the position $b-c\geq y \geq 0$ is mapped to $(y-kb)+(kb+c) = y + c$, and $b-1\leq y+c \geq c$ which is within range.
Case 2: $y \equiv xa \equiv b-1,b-2,...,b-c+1$
The grasshopper moves $b$ places backwards $k+1$ times, thus the position $b-1\leq y \geq b-c$ is mapped to $(y-(k+1)b)+(kb+c) = y+c-b$, and $c-1\geq y+c-b \geq 1$ which is within range.
Case 3: $y \equiv xa \equiv b-c$
Then y is mapped to 0, which is also in the range.
Furthermore, since all the positions in the range $[0,...,b-1]$ can be obtained, with maximum position $b-1$, this implies that $1-a$ is the minimal position, when $y \equiv b-c+1$ and the grasshopper moves $b$ positions backwards $k+1$ times.
Thus, for every position within $[0,b-1]$, after moving backwards $b$ steps some number of times, then moving forward $a$ steps, the grasshopper remains in this interval. We can then conclude the minimum is $1-a$, and the maximum is $b-1$, and that he visits every position between these two points.
overlooked the obvious, mine was so much more complex...
MarkBcc168
13.11.2019 12:59
After the $n$-th minute, the grasshopper is at the position
$$a\left\lfloor\frac{n}{a}\right\rfloor - b\left\lfloor\frac{n}{b}\right\rfloor = [n\pmod b] - [n\pmod a].$$By Chinese Remainder Theorem, the pairs $(n\pmod a, n\pmod b)$ visits all elements in $\{0,1,\hdots,a-1\}\times\{0,1\hdots,b-1\}$. Thus it's easy to see that the answer is $[1-a,b-1]\cap\mathbb{Z}$.