Track / Stage 6 / 112 of 400 #1592 of 2444

Problem 1592

National Olympiad, first round

Combinatorics Difficulty 6.2 Prove it Taiwan IMO Selection Camp · Taiwan · 2021

Let $n$ be a positive odd number. The set of lattice points on the plane $C = \{(i,j): i,j = 0,1,\dots,2n-1\}$ forms a $2n \times 2n$ array, with a guinea pig sitting on each point, each facing one of the positive $x$ -axis direction, negative $x$ -axis direction, positive $y$ -axis direction, or negative $y$ -axis direction. Jeff wants to keep $n^2+1$ of these guinea pigs and remove the rest.
Then the guinea pigs make the following movement: in each round, every guinea pig that has been kept simultaneously moves forward one unit length in the direction it is facing, while maintaining its facing direction; but if a guinea pig is about to move to a point $(i,j) \notin C$ , then it instead moves to $(p,q) \in C$ , where $p \equiv i \pmod{2n}$ and $q \equiv j \pmod{2n}$ (for example, if a guinea pig climbs from $(2,0)$ toward $(2,-1)$ , then it instead climbs to $(2,2n-1)$ .)
Jeff's goal is to ensure that among all the remaining guinea pigs, at no round will two guinea pigs have the same destination point, nor will two guinea pigs climb to each other's starting point for that round.
Prove that: regardless of how the initial guinea pigs' facing directions are distributed, Jeff can always achieve his goal.

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

First represent the guinea pigs' facing directions with arrows, and color them black (B) or white (W) in the manner of a chessboard coloring. In this way we obtain eight kinds of arrows: $B \to$ , $B \leftarrow$ , $B \uparrow$ , $B \downarrow$ , $W \to$ , $W \leftarrow$ , $W \uparrow$ , $W \downarrow$ .

Note that if two guinea pigs are one black and one white, and are in the same or perpendicular directions, then they will never stop at the same point. Thus we obtain twelve combinations of guinea pigs that will not collide:
$\begin{align*} & (B \uparrow, W \uparrow), (B \downarrow, W \downarrow), (B \leftarrow, W \leftarrow), (B \to, W \to), \\ & (B \uparrow, W \to), (B \downarrow, W \to), (B \leftarrow, W \uparrow), (B \to, W \uparrow), \\ & (B \uparrow, W \leftarrow), (B \downarrow, W \leftarrow), (B \leftarrow, W \downarrow), (B \to, W \downarrow). \end{align*}$

Since every arrow is counted three times among these twelve combinations, there must be some combination among these twelve non-colliding pairs whose count of pairs is no less than $\frac{3(2n \times 2n)}{12} = n^2$ .

In fact, there must be some non-colliding pair combination with more than $n^2$ pairs. This is because, if not, then every combination would have exactly $n^2$ pairs. This would mean that the numbers of $B \uparrow$ , $B \downarrow$ , $B \leftarrow$ , and $B \to$ are all exactly equal. But this is impossible, because the total number of black arrows is $\frac{2n \times 2n}{2} = 2n^2$ , which is not divisible by 4. Hence there must be some non-colliding combination with at least $n^2+1$ pairs, and thus the original proposition is proved.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.