Library / Dutch Mathematical Olympiad /22 of 31

Dutch Mathematical Olympiad

Combinatorics Difficulty 6.6 National Olympiad Prove it Netherlands

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

Solution

We distinguish different cases for $n$ based on the remainder of $n$ when dividing by $3$ .

If $n = 3k$ , then the grasshopper can jump as follows:
$1; 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 $2$ on the way back, and then over triples plus $1$ on the second way out.

If $n = 3k + 1$ , then the grasshopper can jump as follows:
$1; 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 + 2$ , we find that the grasshopper can jump as follows:
$1, 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 $n \ge 9$ we have that $k \ge 3$ . In the solutions above for $k \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.