Kvant Math Problem 226
Place the square in the coordinate plane with vertices
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m11s
Source on kvant.digital
Problem
Three grasshoppers are located at three vertices of a square. They are playing leapfrog. If grasshopper $A$ jumps over grasshopper $B$, then after the jump it ends up at the same distance from $B$ (but, naturally, on the other side and on the same line; Fig. 1). Can one of the grasshoppers reach the fourth vertex of the original square after several jumps?
Figure
Yu. I. Ionin
Exploration
Place the square in the coordinate plane with vertices
$$(0,0),\ (1,0),\ (1,1),\ (0,1).$$
Suppose initially the three grasshoppers occupy
$$(0,0),\ (1,0),\ (0,1),$$
and the empty vertex is $(1,1)$.
If a grasshopper at $A$ jumps over a grasshopper at $B$, then its new position is
$$A' = 2B-A.$$
Thus every jump is an affine transformation preserving the integer lattice: if $A$ and $B$ have integer coordinates, then $A'$ also has integer coordinates.
The question is not whether the fourth vertex can be occupied at some moment by any grasshopper, because the fourth vertex already has integer coordinates. A stronger invariant is needed.
Consider the parity of the coordinates. Reduce all coordinates modulo $2$. Initially the occupied residue classes are
$$(0,0),\ (1,0),\ (0,1).$$
The missing class is $(1,1)$.
Under a jump,
$$A' = 2B-A \equiv -A \equiv A \pmod 2,$$
since $-1\equiv 1 \pmod 2$. Hence the residue class modulo $2$ of the jumping grasshopper does not change. The other two grasshoppers do not move. Therefore the multiset of residue classes occupied by the three grasshoppers is invariant.
Since initially no grasshopper occupies the class $(1,1)$, none ever will. The fourth vertex of the original square belongs exactly to that class.
The only point requiring care is to prove rigorously that every grasshopper keeps its own parity class throughout the game.
Problem Understanding
We have three grasshoppers on three vertices of a square. A legal move consists of choosing one grasshopper $A$ and another grasshopper $B$; $A$ jumps over $B$ and lands at the point symmetric to its starting position with respect to $B$. The question is whether, after some sequence of such jumps, one of the grasshoppers can arrive at the fourth vertex of the original square.
This is a Type B problem, a pure proof problem. We must show either that such a sequence exists or that it does not.
The core difficulty is finding an invariant preserved by every jump. The natural invariant is the pair of coordinate parities modulo $2$.
Proof Architecture
The proof uses two claims.
Lemma 1. If a grasshopper at $A$ jumps over a grasshopper at $B$, then its new position is $A'=2B-A$; this is the coordinate description of the jump.
Lemma 2. For every grasshopper, the parity of each coordinate remains unchanged after every jump; modulo $2$, $A'=2B-A\equiv A$.
From Lemma 2, each grasshopper remains forever in the same residue class modulo $2$ as its initial position. Initially the three occupied residue classes are $(0,0)$, $(1,0)$, and $(0,1)$, while the fourth vertex belongs to $(1,1)$. Hence no grasshopper can ever reach that vertex.
The most delicate point is Lemma 2, because the entire argument rests on the parity invariant.
Solution
Assign coordinates to the square so that its vertices are
$$(0,0),\quad (1,0),\quad (0,1),\quad (1,1).$$
Assume the grasshoppers initially occupy
$$(0,0),\quad (1,0),\quad (0,1),$$
and the unoccupied vertex is
$$(1,1).$$
Consider a jump. Let $A$ be the jumping grasshopper and $B$ the grasshopper over which it jumps. Since $B$ is the midpoint of the segment joining the initial and final positions of $A$, the final position $A'$ satisfies
$$B=\frac{A+A'}2.$$
Hence
$$A'=2B-A.$$
Now reduce coordinates modulo $2$. Since $2B\equiv(0,0)\pmod 2$,
$$A' = 2B-A \equiv -A \pmod 2.$$
Because $-1\equiv 1\pmod 2$,
$$-A\equiv A\pmod 2.$$
Therefore
$$A'\equiv A\pmod 2.$$
Thus the parity of each coordinate of the jumping grasshopper is unchanged by the jump. The other two grasshoppers do not move, so their coordinate parities are unchanged as well. Consequently every grasshopper always remains in the same residue class modulo $2$ as its initial position.
Initially the three grasshoppers occupy the residue classes
$$(0,0),\qquad (1,0),\qquad (0,1).$$
The fourth vertex of the original square is $(1,1)$, which belongs to the residue class
$$(1,1).$$
No grasshopper ever acquires the residue class $(1,1)$, because each grasshopper keeps its initial residue class modulo $2$. Hence no grasshopper can ever reach the fourth vertex of the original square.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the formula $A'=2B-A$. Let
$$A=(x_A,y_A),\qquad B=(x_B,y_B).$$
Since $B$ is the midpoint of $AA'$,
$$x_B=\frac{x_A+x_{A'}}2,\qquad y_B=\frac{y_A+y_{A'}}2.$$
Solving gives
$$x_{A'}=2x_B-x_A,\qquad y_{A'}=2y_B-y_A,$$
hence $A'=2B-A$.
The second delicate step is the parity calculation. Writing
$$A'=(2x_B-x_A,;2y_B-y_A),$$
and reducing modulo $2$,
$$2x_B-x_A\equiv -x_A\equiv x_A,$$
$$2y_B-y_A\equiv -y_A\equiv y_A.$$
Thus both coordinate parities are preserved. Forgetting that $-1\equiv1\pmod2$ would break the argument.
A direct check on an actual move confirms the invariant. If
$$A=(0,0),\qquad B=(1,0),$$
then
$$A'=(2,0).$$
Both $A$ and $A'$ have parity class $(0,0)$. The same happens for every possible jump.
Alternative Approaches
Instead of tracking coordinate parities, one may color the entire integer lattice with four colors according to the pair of coordinate parities:
$$(x,y)\mapsto (x\bmod 2,\ y\bmod 2).$$
A jump sends $A$ to $2B-A$, and this point has the same color as $A$. Hence each grasshopper remains forever on squares of its own color. The three initial vertices have three different colors, while the fourth vertex has the missing fourth color. Since no grasshopper can change color, the fourth vertex can never be reached.
This is essentially the same invariant expressed geometrically. The coordinate proof is preferable because the preservation of parity follows immediately from the formula $A'=2B-A$.