Track / Stage 9 / 68 of 80 #1948 of 2000

Problem 1948

IMO P2/P5; hard shortlist

Combinatorics Difficulty 9.3 Prove it 53rd International Mathematical Olympiad Shortlisted Problems with Solutions · IMO

The columns and the rows of a $3n \times 3n$ square board are numbered $1, 2, \ldots, 3n$ . Every square $(x, y)$ with $1 \leq x, y \leq 3n$ is colored asparagus, byzantium or citrine according as the modulo $3$ remainder of $x+y$ is $0$ , $1$ or $2$ respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3n^{2}$ tokens of each color.

Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Without loss of generality it suffices to prove that the A-tokens can be moved to distinct A-squares in such a way that each A-token is moved to a distance at most $d+2$ from its original place. This means we need a perfect matching between the $3n^{2}$ A-squares and the $3n^{2}$ A-tokens such that the distance in each pair of the matching is at most $d+2$ .

To find the matching, we construct a bipartite graph. The A-squares will be the vertices in one class of the graph; the vertices in the other class will be the A-tokens.

Split the board into $3 \times 1$ horizontal triminos; then each trimino contains exactly one A-square. Take a permutation $\pi$ of the tokens which moves A-tokens to B-tokens, B-tokens to C-tokens, and C-tokens to A-tokens, in each case to a distance at most $d$ . For each A-square $S$ , and for each A-token $T$ , connect $S$ and $T$ by an edge if $T$ , $\pi(T)$ or $\pi^{-1}(T)$ is on the trimino containing $S$ . We allow multiple edges; it is even possible that the same square and the same token are connected with three edges. Obviously the lengths of the edges in the graph do not exceed $d+2$ . By length of an edge we mean the distance between the A-square and the A-token it connects.

Each A-token $T$ is connected with the three A-squares whose triminos contain $T$ , $\pi(T)$ and $\pi^{-1}(T)$ . Therefore in the graph all tokens are of degree $3$ . We show that the same is true for the A-squares. Let $S$ be an arbitrary A-square, and let $T_{1}, T_{2}, T_{3}$ be the three tokens on the trimino containing $S$ . For $i=1,2,3$ , if $T_{i}$ is an A-token, then $S$ is connected with $T_{i}$ ; if $T_{i}$ is a B-token then $S$ is connected with $\pi^{-1}\left(T_{i}\right)$ ; finally, if $T_{i}$ is a C-token then $S$ is connected with $\pi\left(T_{i}\right)$ . Hence in the graph the A-squares also are of degree $3$ .

Since the A-squares are of degree $3$ , from every set $\mathcal{S}$ of A-squares exactly $3|\mathcal{S}|$ edges start. These edges end in at least $|\mathcal{S}|$ tokens because the A-tokens also are of degree $3$ . Hence every set $\mathcal{S}$ of A-squares has at least $|\mathcal{S}|$ neighbors among the A-tokens.

Therefore, by Hall's marriage theorem, the graph contains a perfect matching between the two vertex classes. So there is a perfect matching between the A-squares and A-tokens with edges no longer than $d+2$ . It follows that the tokens can be permuted as specified in the problem statement.

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