I’m not dead, I was just in a spree and recently they had a good one in Mexico city. This last week they celebrated the 33th Mexican Math Olympiad in the capital of the city and the exam was as beautiful as it can be. I’m not showing the whole thing ’cause nobody got time for that, but I love number theory and because of that I would like to show you a nice problem; the fifth one.
This one is a nice one that can be solved with some of the basics in number theory. I really encourage you to try it before reading what I did. Here it goes:
Let be two integers, relatively primes between them. We have a line with all integers marked in order from left to right:
A clock is marking each minute, starting at 1, and a grasshopper jumps around, starting at the 0th mark, following these rules:
- If the current minute is multiple of , but not a multiple of , the grasshopper jumps numbers to the right.
- If the current minute is multiple of , but not a multiple of , the grasshopper jumps numbers to the left.
- If the current minute is multiple of and , the grasshopper jumps numbers to the right.
- In every other instant, the grasshopper doesn’t move.
The grasshopper moves at most once per minute, of course. Determine the sites which the grasshopper can jump to.
That’s it! A short note before starting: This solution was done with the help of Leonardo Martinez in a bar the day of the exam. It is really similar to the official solutions presented during the contest, but I write it here with the thinking process that took us to the solution at the moment. Here we go!
First we notice that, if at time , the grasshopper does a certain movement, it would do exactly the same movement at time . Then, we can focus on the time from 1 to , since after this, the movement will just repeat.
Now, what will happen after those first minutes? Does the grasshopper displaces somewhere apart from zero or does he stays in the same place repeating the same steps? Well, since and don’t have any common factor, the only any a number can be multiple of both is if it is a multiple of . This means that during the first minutes:
- The grasshopper has performed jumps of units to the right.
- The grasshopper has performed jumps of units to the left.
- The grasshopper has performed 1 jump of units to the right.
Then, the grasshopper ends up at position . Perfect! At the end of the day, the grasshopper comes back to its starting position. From this we just need to know which are the position visited between minute 1 and and those ones will be all the possible ones. Notice as well that the grasshopper jumped times during the first minutes.
It is not obvious to know how to proceed without some kind of conjecture. This is a good moment to plug some values into and to see how it behaves. I confess we try many combinations before getting the correct conjecture, but here I’ll just show you the most illuminating one. Consider and , let’s study how does the first 12 minutes look:
Minute | Final Position | Minute | Final Position |
1 | 0 | 7 | -2 |
2 | 0 | 8 | 2 |
3 | -3 | 9 | -1 |
4 | 1 | 10 | -1 |
5 | 1 | 11 | -1 |
6 | -2 | 12 | 0 |
If you do this with other similar cases you can easily notice that you choose every integer within a certain interval: For and 4 and 3 you have all the integer between -3 and 2. For 7 and 2, you obtain all integers between -6 and 1… do you see it?
The grasshopper gets to every integer larger than and smaller than .
Good! now we have a conjecture. Let’s see if it is true. Notice that between this two numbers, we have exactly integers. However, we said that this is the amount of jumps the grasshopper does. This means that, if our hypothesis is true, we need every jump to lead to a number that has not been visited before (except for the last one that goes back to zero of course). We will try to prove that first using the following lemma:
Lemma 1. Let and be integer such that . Let and integers such that:
then is multiple of and is a multiple of
Lemma’s proof: From the equation: . This tells us that , but . Thus as we wanted. Similarly for .
Easy! Now, let’s consider the positions that the grasshopper gets to during the first minutes. The numbers in such positions take the form , where and are the number of jumps to the right and to the left, respectively. From what we have discussed above, we can see that:
and
It follows that every time that we jump to another position, we get to a place we haven’t visited, why? because if we were to repeat a number, that number would be able to be written in that form in two different ways as in . If this was the case, due to the lemma, the ‘s coefficients would need to differ by at least , while at the same time being both smaller than , which is absurd. Thus, we don’t repeat numbers.
Fantastic, we are almost finished. Up to this moment we have shown that the grasshopper visits different integers in minutes, including zero. We also know that, in principle, we are not that far from zero, since we should be able to come back to it at the end of the trip. This is the last idea that we need to finish the problem.
Now, how far to the left can he jump ? Let’s that up to a certain moment, the grasshopper has have jumps to the left. This means that is has have at least jumps to the right (the number of multiples of smaller than ). From this, the farthest to the left that we could be is . But it is not hard to see that . By replacing this in the inequality, the farthest that the grasshopper could get is: . This is what we wanted to prove in our conjecture: All numbers that are visited by the grasshopper are larger than .
Now, how far to the right can he jump ? Let’s that up to a certain moment, the grasshopper has have jumps to the right. This means that is has have at least jumps to the left (the number of multiples of smaller than ). From this, the farthest to the right that we could be is . But it is not hard to see that . By replacing this in the inequality, the farthest that the grasshopper could get is: . This is the last thing we wanted to prove!: All numbers that are visited by the grasshopper are smaller than .
Putting things together, we know that:
- The grasshopper visits different integers in minutes, including zero.
- All numbers that are visited are larger than .
- All numbers that are visited are smaller than .
Then it is clear that the grasshopper visits every number between and once every minutes!
But wait! Don’t leave yet! I have a special little surprise for you in this problem:
The beautiful Bezout’s lemma.
The problem we just solve gives us a beautiful result:
Theorem (Little Bezout). Let be positive integers relatively primes. There exist a unique linear combination of them such that:
with and
Fantastic, isn’t it? Let’s go one step further. Consider a linear combination of integers such that , say . We see that , which allows us to rewrite this equation as:
with an integer
By the little Bezout’s theorem, there exist and smaller than and , respectively such that
or, equivalently, .
By multipliying this equation by we recover . This allows us to recover a much stronger statement than before:
Theorem (Bezout’s Identity). Let be positive integers. There exist a unique linear combination of them such that:
with and
More over, the equation has a solution for a given if and only if
Marvelous!
After this, I don’t think I can say anything more interesting to top it off, so I’ll conclude here. See you soon.
Errata: There was a subtle mistake in the original post of this proof that came from trying to simplify the argument.The original text said:
How far to the left can the grasshopper go ? Well, since and they are not multiples of each other, Euclid’s division lemma tells us that we can write for some integers and . From this we see that the grasshopper stars jumping times to the left until it gets to and then jumps to the right until it gets to . He then jumps again at most times to the left before jumping back to the right. However, this second time he had started at instead of zero, so he couldn’t have gone as far to the left as in the first time. By this argument we can see that the farthest to the left that the grasshopper gets is actually on his first round of jumps to the left, where we gets to . This is what we wanted to prove in our conjecture: All numbers that are visited by the grasshopper are larger than .
The problem with this is that when the grasshopper jumps to the left, sometime it does it times, but sometimes it does it . This gives a rather easier, but faulty proof that the grasshopper gets to numbers larger than . Originally, we used the version you now found in the text, but changed it while ignoring this fact. Thanks to Omar Antolín Camarena for pointing the mistake. Apparently it was a common mistake and it may be more useful to point it out here.