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 Idef=[−(a−1),+(b−1)].
Claim. The grasshopper never leaves the interval I.
Proof. Let's prove that it never takes on a value ≥b (similar proof for ≤−a). After the tth minute, it moves +a ⌊ta⌋ times and −b ⌊tb⌋ times, so the net displacement is
a⌊ta⌋−b⌊tb⌋<a⋅ta−b(tb−1)=b,as desired.
Now observe that for any integer n∈I, exactly one of n+a∈I and n−b∈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↦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∈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}.