Maths Olympiad Prep

Library / /3 of 4

Combinatorics Difficulty 6.9 National Olympiad Prove it Italy

Problem:

A grasshopper moves on the plane and from the point with coordinates (x,y)(x, y) it can jump, at its choice, either to (x+y,y)(x+y, y) or to (x,x+y)(x, x+y). It started from a point with coordinates (n,9)(n, 9) with nn a positive integer, but it does not remember the value of nn. It only knows that after a certain number of moves it arrived at (2021,2050)(2021,2050). How many possible values of nn are there?

Solution

Solution:

The answer is 3. In general, if at a certain point the grasshopper is at (a,b)(a, b), at the previous step it was at a point (x,y)(x, y) such that (a,b)=(x+y,y)(a, b) = (x+y, y) or (a,b)=(x,x+y)(a, b) = (x, x+y), that is, at (ab,b)(a-b, b) or at (a,ba)(a, b-a); moreover, if it started from a point (x0,y0)(x_0, y_0) with positive coordinates, as the statement assures us, then at every moment it is located at a point with positive coordinates, and therefore the position preceding (a,b)(a, b) is uniquely determined and is (ab,b)(a-b, b) if a>ba > b, (a,ba)(a, b-a) if b>ab > a.

It follows that the positions of the grasshopper preceding (2021,2050)(2021,2050), going backwards, are: (2021,20502021)=(2021,29)(2021,2050-2021) = (2021,29), (202129,29)(2021-29,29), (2021229,29)(2021-2 \cdot 29,29), \ldots, (20216929,29)=(20,29)(2021-69 \cdot 29,29) = (20,29), (20,2920)=(20,9)(20,29-20) = (20,9). The grasshopper could therefore have started from (20,9)(20,9); if it did not, it could have made one more jump and started from (209,9)=(11,9)(20-9,9) = (11,9) or two more jumps and started from (119,9)=(2,9)(11-9,9) = (2,9). If the grasshopper had made even more jumps, it would have started from a point whose second coordinate is at most 7, which does not satisfy the conditions of the statement. There are therefore 3 possibilities for (x0,y0)(x_0, y_0).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.