Maths Olympiad Prep

Library / /8 of 31

Number theory Difficulty 8.1 Shortlist Prove it Baltic Way

A grasshopper is jumping along the set Z\mathbb{Z} of integers. He starts at the origin; and for each jump, he may decide whether to jump to the left or to the right. For each nN0n \in \mathbb{N}_0, the nn-th jump has length n2n^2.
Prove or disprove that for each kZk \in \mathbb{Z} the grasshopper can arrive at kk starting from origin.

Solution

Clearly, the grasshopper can arrive at the integers +1+1 and 1-1, in one jump. And also, he can arrive at the integer 1414 using three jumps to the right (1+4+9=141 + 4 + 9 = 14).
Note the following: if the grasshopper can arrive at a number aZa \in \mathbb{Z} using nn jumps, then he can also arrive at the numbers a4a-4 and a+4a+4 using n+4n+4 jumps, by jumping left, right, right, left (for a4a-4), and right, left, left, right (for a+4a+4), because of
a(n+1)2+(n+2)2+(n+3)2(n+4)2=a4, a - (n + 1)^2 + (n + 2)^2 + (n + 3)^2 - (n + 4)^2 = a - 4,
a+(n+1)2(n+2)2(n+3)2+(n+4)2=a+4. a + (n + 1)^2 - (n + 2)^2 - (n + 3)^2 + (n + 4)^2 = a + 4.
Since the numbers 00, +1+1, 1-1 and 1414 all have distinct remainders modulo four, the grasshopper can arrive at each integer in a finite number of jumps.

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 and solution reproduced as published; topic and difficulty added by this site.