A little jump to the left

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 a > b be two integers, relatively primes between them. We have a line with all integers marked in order from left to right:

line

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 a , but not a multiple of b , the grasshopper jumps a numbers to the right.
  • If the current minute is multiple of b , but not a multiple of a  , the grasshopper jumps b numbers to the left.
  • If the current minute is multiple of a and b , the grasshopper jumps a - b 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 t , the grasshopper does a certain movement, it would do exactly the same movement at time t+ab . Then, we can focus on the time from 1 to ab , since after this, the movement will just repeat.

Now, what will happen after those first ab minutes? Does the grasshopper displaces somewhere apart from zero or does he stays in the same place repeating the same steps? Well, since a and b don’t have any common factor, the only any a number can be multiple of both is if it is a multiple of ab . This means that during the first ab minutes:

  • The grasshopper has performed b-1 jumps of a units to the right.
  • The grasshopper has performed a-1 jumps of b units to the left.
  • The grasshopper has performed 1 jump of a-b units to the right.

Then, the grasshopper ends up at position a(b-1)-b(a-1)+(a-b)=0 . 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 ab and those ones will be all the possible ones. Notice as well that the grasshopper jumped (b-1)+(a-1)+1=a+b-1 times during the first ab 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 a and b 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 a=4   and b=3 , 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 a and b 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 -a and smaller than b .

Good! now we have a conjecture. Let’s see if it is true. Notice that between this two numbers, we have exactly (b-1)+(a-1)+1=a+b-1 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 a and b   be integer such that (a,b)=1 . Let x_1,x_2,y_1 and y_2 integers such that:

\displaystyle ax_1+by_1=ax_2+by_2

then x_1-x_2 is multiple of b and y_1-y_2   is a multiple of  a

Lemma’s proof: From the equation: a(x_1-x_2)=b(y_2-y_1) . This tells us that a|b(y_2-y_1) , but (a,b)=1 . Thus a|y_2-y_1 as we wanted. Similarly for b .

Easy! Now, let’s consider the positions that the grasshopper gets to during the first ab minutes. The numbers in such positions take the form ax-by , where x and y are the number of jumps to the right and to the left, respectively. From what we have discussed above, we can see that:

\displaystyle 0 \leq x < b  and \displaystyle 0 \leq y < a 

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 ax_1+by_1=ax_2+by_2 . If this was the case, due to the lemma, the a ‘s coefficients would need to differ by at least b , while at the same time being both smaller than b , 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 a+b-1 different integers in ab   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 y  jumps to the left. This means that is has have at least \left\lfloor{\frac{by}{a}} \right\rfloor jumps to the right (the number of multiples of a  smaller than by  ). From this, the farthest to the left that we could be is -by+a\left\lfloor{\frac{by}{a}} \right\rfloor . But it is not hard to see that \left\lfloor{\frac{by}{a}} \right\rfloor >\frac{by}{a}-1 . By replacing this in the inequality, the farthest that the grasshopper could get is: -by+a\left\lfloor{\frac{by}{a}} \right\rfloor > -by+a\left(\frac{by}{a}-1\right)) =-a . This is what we wanted to prove in our conjecture: All numbers that are visited by the grasshopper are larger than -a .

Now, how far to the right can he jump ? Let’s that up to a certain moment, the grasshopper has have x  jumps to the right. This means that is has have at least \left\lfloor{\frac{ax}{b}} \right\rfloor jumps to the left (the number of multiples of b  smaller than ax  ). From this, the farthest to the right that we could be is ax-b\left\lfloor{\frac{ax}{b}} \right\rfloor . But it is not hard to see that \left\lfloor{\frac{ax}{b}} \right\rfloor >\frac{ax}{b}-1 . By replacing this in the inequality, the farthest that the grasshopper could get is: ax-b\left\lfloor{\frac{ax}{b}} \right\rfloor < ax-b\left(\frac{ax}{b}-1\right)) =b . This is the last thing we wanted to prove!: All numbers that are visited by the grasshopper are smaller than b .

Putting things together, we know that:

  • The grasshopper visits a+b-1 different integers in ab   minutes, including zero.
  • All numbers that are visited are larger than -a .
  • All numbers that are visited are smaller than b .

Then it is clear that the grasshopper visits every number between -a and b once every ab minutes!  \square

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 a>b be positive integers relatively primes. There exist a unique linear combination of them such that:

\displaystyle ax-by=1 with 0<x<b and 0<y<a

Fantastic, isn’t it? Let’s go one step further. Consider a linear combination of integers a>b such that (a,b)=d , say ax+by=c . We see that d|c , which allows us to rewrite this equation as:

\displaystyle ax+by=d\frac{c}{d} with \frac{c}{d} an integer

By the little Bezout’s theorem, there exist x_0   and y_0 smaller than b' and a' , respectively such that

\displaystyle a'x_0-b'y_0=1 or, equivalently, \displaystyle ax_0-by_0=d .

By multipliying this equation by \frac{c}{d} we recover a\left(x_0\frac{c}{d}\right)+b(-y_0\frac{c}{d})=c . This allows us to recover a much stronger statement than before:

Theorem (Bezout’s Identity). Let a>b be positive integers. There exist a unique linear combination of them such that:

\displaystyle ax-by=(a,b) with 0<x<\frac{b}{(a,b)} and 0<y<\frac{a}{(a,b)}

More over, the equation ax+by=c has a solution for a given c if and only if (a,b)|c

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 a > b and they are not multiples of each other, Euclid’s division lemma tells us that we can write a = bq+r for some integers 1 \leq q  and 0< \leq r < b  . From this we see that the grasshopper stars jumping q  times to the left until it gets to -qb  and then jumps to the right until it gets to r  . He then jumps again at most q  times to the left before jumping back to the right. However, this second time he had started at r  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 -qb=r-a>-a  . This is what we wanted to prove in our conjecture: All numbers that are visited by the grasshopper are larger than -a .

The problem with this is that when the grasshopper jumps to the left, sometime it does it q times, but sometimes it does it q +1 . This gives a rather easier, but faulty proof that the grasshopper gets to numbers larger than -a . 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.

Leave a comment