Library / /241 of 397

, 2021

Combinatorics Difficulty 6.2 National Olympiad Prove it Taiwan

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.

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.

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 translated into English from zh; metadata (topic, difficulty) added by this project.