Maths Olympiad Prep

Library / /10 of 10

Combinatorics Difficulty 9.0 IMO level Prove it United States

In a table with nn rows and 2n2n columns where nn is a fixed positive integer, we write either zero or one into each cell so that each row has nn zeros and nn ones. For 1kn1 \le k \le n and 1in1 \le i \le n, we define ak,ia_{k,i} so that the iith zero in the kkth row is the ak,itha_{k,i}^{th} column. Let F\mathcal{F} be the set of such tables with a1,ia2,ian,ia_{1,i} \ge a_{2,i} \ge \dots \ge a_{n,i} for every ii with 1in1 \le i \le n. We associate another n×2nn \times 2n table f(C)f(C) from CFC \in \mathcal{F} as follows: for the kkth row of f(C)f(C), we write nn ones in the columns an,kk+1,an1,kk+2,,a1,kk+na_{n,k} - k + 1, a_{n-1,k} - k + 2, \dots, a_{1,k} - k + n (and we write zeros in the other cells in the row).

a. Show that f(C)Ff(C) \in \mathcal{F}.

b. Show that f(f(f(f(f(C)))))=Cf(f(f(f(f(C))))) = C for any CFC \in \mathcal{F}.

Solution

We first give a bijection between tables CFC \in \mathcal{F} and partitions of a fixed regular hexagon of side length nn into parallelograms given by two unit equilateral triangles glued together. Call such a partition a well-partitioned hexagon. For a well-partitioned hexagon, align one of its edges parallel to the yy axis so that the hexagon lies to the right side of this edge and divide it into nn unit edges.

Consider the first unit edge on the top, which is an edge of a unit parallelogram. Connect the midpoint M0M_0 of this edge to the midpoint M1M_1 of the opposite edge of this parallelogram. We write 1 in the (1,1) cell of an empty n×2nn \times 2n table CC if M0M1M_0 M_1 has positive slope, and 0 otherwise. Similarly, we take M2M_2 to be the next midpoint and write 1 or 0 in the (1,2) cell if M1M2M_1 M_2 has positive slope or not, respectively. Iterate this step 2n2n times to fill the first row of CC with 0's and 1's. We do the same thing for the second unit edge on the left edge of HH to fill the second row of CC, and so on. The result is a n×2nn \times 2n table whose cells are filled with 0 or 1. An example of this correspondence is below.

C=[110010101001100011]Hexagon C = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix} \longleftrightarrow \text{Hexagon}

Since the height of the kk-th unit edge on the left edge of HH is the same as the kk-th one on the right edge of HH, the number of 0's and 1's in the kkth row is the same, namely nn. If ak,i<ak+1,ia_{k,i} < a_{k+1,i} for some k,ik, i, let i0i_0 be the minimum of such ii's. Then among the 1,2,,ak,i011, 2, \dots, a_{k,i_0} - 1st columns, the number of 0's in the kkth and k+1k+1st row are the same. Hence, the ak,i01a_{k,i_0} - 1st edge of the kkth row is adjacent to the ak,i01a_{k,i_0} - 1st edge of the kk-th and k+1k+1-th row. But then the next parallelograms of the kk-th and k+1k+1-th row overlap, a contradiction. Hence, we have that CFC \in \mathcal{F}. Similarly, one can check that for any CFC \in \mathcal{F}, one can find a corresponding well-partitioned hexagon HH.

We are now ready to address both parts of the problem.

a. A rotation of a well-partitioned hexagon is still well-partitioned, so f(C)f(C) corresponds to a well-partitioned hexagon, hence lies in F\mathcal{F}.

b. The well-partitioned hexagon associated to f6(C)f^6(C) is simply a rotation of the hexagon associated to CC by 360 degrees, hence is the same as the hexagon associated to CC. Therefore, by our bijection, we find that C=f6(C)C = f^6(C).

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 reproduced verbatim; metadata (topic, difficulty) added by this project.