CombinatoricsDifficulty 9.0IMO levelProve itUnited States
In a table with n rows and 2n columns where n is a fixed positive integer, we write either zero or one into each cell so that each row has n zeros and n ones. For 1≤k≤n and 1≤i≤n, we define ak,i so that the ith zero in the kth row is the ak,ith column. Let F be the set of such tables with a1,i≥a2,i≥⋯≥an,i for every i with 1≤i≤n. We associate another n×2n table f(C) from C∈F as follows: for the kth row of f(C), we write n ones in the columns an,k−k+1,an−1,k−k+2,…,a1,k−k+n (and we write zeros in the other cells in the row).
a. Show that f(C)∈F.
b. Show that f(f(f(f(f(C)))))=C for any C∈F.
Solution
We first give a bijection between tables C∈F and partitions of a fixed regular hexagon of side length n 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 y axis so that the hexagon lies to the right side of this edge and divide it into n unit edges.
Consider the first unit edge on the top, which is an edge of a unit parallelogram. Connect the midpoint M0 of this edge to the midpoint M1 of the opposite edge of this parallelogram. We write 1 in the (1,1) cell of an empty n×2n table C if M0M1 has positive slope, and 0 otherwise. Similarly, we take M2 to be the next midpoint and write 1 or 0 in the (1,2) cell if M1M2 has positive slope or not, respectively. Iterate this step 2n times to fill the first row of C with 0's and 1's. We do the same thing for the second unit edge on the left edge of H to fill the second row of C, and so on. The result is a n×2n table whose cells are filled with 0 or 1. An example of this correspondence is below.
C=111100010000101011⟷Hexagon
Since the height of the k-th unit edge on the left edge of H is the same as the k-th one on the right edge of H, the number of 0's and 1's in the kth row is the same, namely n. If ak,i<ak+1,i for some k,i, let i0 be the minimum of such i's. Then among the 1,2,…,ak,i0−1st columns, the number of 0's in the kth and k+1st row are the same. Hence, the ak,i0−1st edge of the kth row is adjacent to the ak,i0−1st edge of the k-th and k+1-th row. But then the next parallelograms of the k-th and k+1-th row overlap, a contradiction. Hence, we have that C∈F. Similarly, one can check that for any C∈F, one can find a corresponding well-partitioned hexagon H.
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) corresponds to a well-partitioned hexagon, hence lies in F.
b. The well-partitioned hexagon associated to f6(C) is simply a rotation of the hexagon associated to C by 360 degrees, hence is the same as the hexagon associated to C. Therefore, by our bijection, we find that C=f6(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.