Track / Stage 5 / 380 of 400 #1460 of 2444

Problem 1460

AIME late

Combinatorics Difficulty 6.0 Prove it Taiwan IMO Selection Camp · Taiwan

A $3n \times 3n$ chessboard has its rows and columns numbered in order from 1 to $3n$ . The square $(x, y)$ is colored A, B, or C according to whether $x + y$ modulo 3 has remainder 0, 1, or 2, respectively. A chip is placed on every square, and each chip has color A, B, or C. There are $3n^2$ chips of each of the three colors.
Suppose we can arrange a rearrangement of the chips satisfying the following: each chip moves a distance of at most $d$ , chips of color A replace chips of color B, chips of color B replace chips of color C, and chips of color C replace chips of color A. Prove that there is another rearrangement of the chips such that each chip moves a distance of at most $d+2$ , and after the move every square contains a chip of the same color as that square.

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

Without loss of generality, it suffices to prove that all the color-A chips (abbreviated as A-chips) can be moved to distinct color-A squares (abbreviated as A-squares), such that each A-chip moves a distance of at most $d+2$ from its original square. That is to say, we can form a perfect matching between the $3n^2$ A-chips and the $3n^2$ A-squares such that the distance between each matched pair is at most $d+2$ .
In order to find this perfect matching, we construct a bipartite graph: all the A-squares form one group of vertices, and all the A-chips form another group of vertices.
Divide the original chessboard into $3 \times 1$ trominoes; each tromino contains exactly one A-square. Find a permutation $\pi$ that sends A-chips to B-chips, B-chips to C-chips, and C-chips to A-chips, such that every move has distance at most $d$ . For any A-square $S$ and any A-chip $T$ , if $\pi(T)$ or $\pi^{-1}(T)$ lies in the tromino containing $S$ , then we connect $S$ and $T$ with an edge in the bipartite graph. It is easy to see that this graph may have multiple edges; a square and a chip may be connected by up to three edges. It is easy to see that every edge in the graph has length at most $d+2$ ; here the length of an edge refers to the distance between the square and the chip it connects.
Every A-chip $T$ is connected to three A-squares: these are the A-squares belonging to the trominoes that contain $T$ , $\pi(T)$ , and $\pi^{-1}(T)$ . Hence in this bipartite graph, every chip has degree 3. Next we prove that every square also has degree 3. Let $S$ be some A-square, and let $T_1, T_2, T_3$

be the chips on the tromino containing $S$ . For $i = 1, 2, 3$ , if $T_i$ is an A-chip, then $S$ is connected to $T_i$ ; if $T_i$ is a B-chip, then $S$ is connected to $\pi^{-1}(T_i)$ ; and finally if $T_i$ is a C-chip, then $S$ is connected to $\pi(T_i)$ . This proves that every A-square also has degree 3.
Since every A-square has degree 3, from any set $S$ of A-squares there emanate $3|S|$ edges. These edges reach at least $|S|$ chips, because every A-chip also has degree 3. Therefore, any set $S$ of A-squares has at least $|S|$ A-chips as its neighbors.
Thus, by Hall's marriage theorem, there exists a perfect matching between the two groups of vertices in this bipartite graph. Hence there exists a perfect matching between the A-squares and the A-chips in which every edge has distance at most $d+2$ ; therefore the rearrangement required by the original problem exists, which completes the proof.

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