IMO 2012 Shortlist C5

Category: Combinatorics

Problem

The columns and the rows of a 3n × 3n square board are numbered 1,2,...,3n. Every square (x,y) with 1 ≤ x,y ≤ 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 3n2 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. 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 3n2 A-squares and the 3n2 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 × 1 horizontal triminos; then each trimino contains exactly one A- square. Take a permutation π 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, π(T) or π−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, π(T) and π−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 T1,T2,T3 be the three tokens on the trimino containing S. For i = 1,2,3, if Ti is an A-token, then S is connected with Ti; if Ti is a B-token then S is connected with π−1 (Ti); finally, if Ti is a C-token then S is connected with π(Ti). Hence in the graph the A-squares also are of degree 3. Since the A-squares are of degree 3, from every set S of A-squares exactly 3|S| edges start. These edges end in at least |S| tokens because the A-tokens also are of degree 3. Hence every set S of A-squares has at least |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. Comment 1. In the original problem proposal the board was infinite and there were only two colors. Having n colors for some positive integer n was an option; we chose n = 3. Moreover, we changed the board to a finite one to avoid dealing with infinite graphs (although Hall’s theorem works in the infinite case as well). With only two colors Hall’s theorem is not needed. In this case we split the board into 2 × 1 dominos, and in the resulting graph all vertices are of degree 2. The graph consists of disjoint cycles with even length and infinite paths, so the existence of the matching is trivial. Having more than three colors would make the problem statement more complicated, because we need a matching between every two color classes of tokens. However, this would not mean a significant increase in difficulty.25 Comment 2. According to Wikipedia, the color asparagus (hexadecimal code #87A96B) is a tone of green that is named after the vegetable. Crayola created this color in 1993 as one of the 16 to be named in the Name The Color Contest. Byzantium (#702963) is a dark tone of purple. Its first recorded use as a color name in English was in 1926. Citrine (#E4D00A) is variously described as yellow, greenish-yellow, brownish-yellow or orange. The first known use of citrine as a color name in English was in the 14th century.26