Maths Olympiad Prep

Library / /32 of 36

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Netherlands

Mila stands on an infinitely large board divided into squares and starts moving. An nn-jump is a movement in which Mila moves one square left, right, up or down and then nn squares in a direction perpendicular to that. Below is an example where Mila starts in the middle box on the left and first does a 11-jump, followed by a 22-jump and then a 33-jump, 44-jump and 55-jump.
Figure 1
Suppose Mila first does a 11-jump, then a 22-jump, then a 33-jump, a 44-jump, and so on. Finally, she does a mm-jump. For which positive integers mm can Mila choose her mm jumps such that she can get back to her starting square?

Solution

Colour the squares on the board alternately white and black, like on a chess board. If nn is odd, then an nn-jump always goes to a square of the same colour as the starting square, and if nn is even precisely to a square of the other colour. Suppose Mila starts on a white square. If Mila makes a total of mm jumps and starts on a white square, Mila ends on a white square if mm is of the form 4k4k or 4k+14k + 1, where kk is an integer, and on a black square if mm is of the form 4k+24k + 2 or 4k+34k + 3.
So the only possibilities for Mila to end up on the initial square are for mm of the form 4k4k or 4k+14k + 1. In the first case, we see immediately that this is indeed possible from the following claim: for every nn, Mila can return to her starting square after an (n+1)(n+1)-jump, (n+2)(n+2)-jump, (n+3)(n+3)-jump and (n+4)(n+4)-jump. Proof of claim: suppose Mila starts on the square with coordinates (0,0)(0,0). Then Mila can return by first jumping to (1,n+1)(1, n+1), then to (n+3,n+2)(n+3, n+2), then to (n+4,1)(n+4, -1) and finally back to (0,0)(0,0).

For m=1m = 1 it is not possible to end on the square where Mila started, but
for m=5m = 5 it can be done by jumping as follows:
(0,0)(1,1)(2,3)(5,4)(1,5)(0,0). (0, 0) - (1, 1) - (2, 3) - (5, 4) - (1, 5) - (0, 0).

Then by pasting the path from the claim for n=5,9,13,n = 5, 9, 13, \dots, we see that
it is thus possible for Mila to end on the square she started, for mm of the
form 4k+14k + 1, as long as m5m \ge 5.
Together we find that Mila can return to her starting square after mm jumps
for every mm of the form 4k4k or 4k+14k + 1, for m4m \ge 4 (and thus k1k \ge 1).

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.