Maths Olympiad Prep

Library / /24 of 36

Combinatorics Difficulty 6.6 National Olympiad Prove it Netherlands

Let nn be a positive integer. A grasshopper stands on the number line at the number 11 and may make either a jump of length 22 or of length 33 each time. Each time, the grasshopper must land on an integer from 11 through nn where the grasshopper has not been before. The grasshopper would like to visit all integers from 11 through nn exactly once and land on the number nn.
Prove that this can be done for all n9n \ge 9.

Solution

We distinguish different cases for nn based on the remainder of nn when dividing by 33.

If n=3kn = 3k, then the grasshopper can jump as follows:
1;3,6,,3(k1);3(k1)+2,3(k2)+2,,2;4,7,,3(k1)+1;3k1; 3, 6, \ldots, 3(k-1); 3(k-1)+2, 3(k-2)+2, \ldots, 2; 4, 7, \ldots, 3(k-1)+1; 3k.
The grasshopper jumps over triples on the way out, over triples plus 22 on the way back, and then over triples plus 11 on the second way out.

If n=3k+1n = 3k + 1, then the grasshopper can jump as follows:
1;3,6,,3k;3k2,3(k1)2,,7,4;2,5,8,,3(k1)+2;3k+11; 3, 6, \ldots, 3k; 3k-2, 3(k-1)-2, \ldots, 7, 4; 2, 5, 8, \ldots, 3(k-1)+2; 3k+1.

Finally, for n=3k+2n = 3k + 2, we find that the grasshopper can jump as follows:
1,3,6,4;2,5,8,,3(k1)+2;3k+1,3(k1)+1,,7;9,,3k;3k+21, 3, 6, 4; 2, 5, 8, \ldots, 3(k-1)+2; 3k+1, 3(k-1)+1, \ldots, 7; 9, \ldots, 3k; 3k+2.

Because n9n \ge 9 we have that k3k \ge 3. In the solutions above for k3k \ge 3 we see that every leg of the 'zigzag' is nonempty, so a solution exists.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.