Track / Stage 8 / 152 of 180 #1852 of 1964

Problem 1852

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.8 Prove it Baltic Way shortlist · Baltic Way

Let $n$ be a positive integer. Elfie the Elf lives in a three dimensional space $\mathbb{Z}^3$ . She starts at the origin: $(0,0,0)$ . In each turn she can teleport into any point in $\mathbb{Z}^3$ which lies at the distance $\sqrt{n}$ from her current location. However, teleportation is a complicated procedure. Elfie starts off normal but she turns strange with her first teleportation. Next time she teleports she becomes normal again, then strange again... etc.
For which $n$ can Elfie travel to any given point in $\mathbb{Z}^3$ and be normal when she gets there?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Answer: there are no such $n$ .
We colour all the points in $\mathbb{Z}^3$ white and black: The point $(x, y, z)$ is colored white if $x+y+z \equiv_2 0$ and black if $x + y + z \equiv_2 1$ .
After the first move Elfie is at a point $(a, b, c)$ where $a^2 + b^2 + c^2 = n$ . Thus, $a + b + c \equiv_2 n$
Now, if $n$ is even then $(a, b, c)$ is white. Thus, in that case Elfie only jumps between white points.
On the other hand, if $n$ is odd, then $(a, b, c)$ is certainly black. And one can easily see that Elfie alternates between black and white squares after each move. But since Elfie is normal after even number of moves, and is then on a white point, she can never reach any black point being normal. Thus, there no $n$ such that Elfie can travel to any given point and be normal when she gets there.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.