Maths Olympiad Prep

Library / /61 of 63

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Japan

Let nn be a positive integer and suppose a 2n×2n2n \times 2n square grid is given. Suppose we color exactly 2n22n^2 square boxes of the grid in such a way that the following condition is satisfied.

Condition: If a box is colored then none of the boxes which share only a vertex with that box is not colored.

How many ways of coloring 2n22n^2 square boxes of the grid are there that satisfy the condition stated above? We regard two configurations of colored boxes to be distinct if one configuration can be transposed on the other by rotation or by flipping.

Solution

(2nCn)2(2nC_n)^2 ways

Let us consider the n×nn \times n grid of squares of side length 22 obtained from the original grid by forming n2n^2 non-overlapping squares of side length 22 by coalescing 44 neighboring squares of the original grid into one large square. Let us call each of the squares of the new grid a block. By the condition of the problem, each block contains at most 22 squares to be colored, and since 2n22n^2 squares of the original grid must be colored, we see that exactly 22 of the 44 squares in each block must be colored.

Suppose we label 44 squares in a block A,B,C,DA, B, C, D as indicated in the figure below, and do this in the same way for each block.

AB
CD

In order to color 22 of the 44 squares in a block so as to satisfy the condition of the problem, it is enough to choose one of the squares from AA and DD and one of the squares from BB and CC to color.
A square in a block can share a side, or a vertex but not a side, or nothing with any square in an adjacent block (which shares with the block a side or just a vertex). Sharing of a vertex but not a side by two squares in adjacent blocks can occur only when the labels of the two squares are AA and DD or when they are BB and CC.

Therefore, the decision to color which of the squares AA and DD for a block can be made independently of the decision to color BB or CC in that block.

Let us now consider how to decide whether AA or DD should be colored for each block. Let us start off with the block located at the upper-left corner and choose AA or DD in that block to color, and proceed to the block lying to the immediate right of the initial block on the same row to make the choice between AA and DD (so as to satisfy the condition of the problem) and keep on doing the same process until we hit the last block on this row, and then go over to the left-most block lying on the second row to repeat the process, going from left to right, and on to the third row, and so on, finally to reach the last block lying at the lower-right corner. In this process, if for some block XX, the square DD was chosen to be colored, then for all of the blocks lying on the same row and to the right of XX, DD should be colored in order to satisfy the condition of the problem. We also see that if there is a row under the row for XX, then the block lying directly under XX must have the square DD colored.

Consequently, for each k=1,2,,nk = 1, 2, \dots, n, there exists an integer aka_k such that in the kk-th row of the blocks, in all of the nakn - a_k blocks from the left the square AA is colored, while in the remaining aka_k blocks in the same row the square DD is colored. Furthermore, from the condition on the vertically adjacent pairs of the blocks, we see that aka_k's satisfy
0a1a2ann(). 0 \le a_1 \le a_2 \le \dots \le a_n \le n \quad (\dagger).
Conversely, if for such a sequence {ak;1kn}\{a_k; 1 \le k \le n\} we color the square AA or DD in the kk-th row so that for all of the first nakn - a_k blocks from the left the square AA will be colored and for the remaining aka_k blocks in the same row the square DD will be colored, and we do this for every k=1,2,,nk = 1, 2, \dots, n, then the condition of the coloring will be satisfied as far as the squares AA and DD are concerned.

If we define, for each k=1,2,,nk = 1, 2, \dots, n, bk=ak+kb_k = a_k + k the inequalities ()(\dagger) above are equivalent to
1b1<b2<<bn2n, 1 \le b_1 < b_2 < \dots < b_n \le 2n,
and therefore, we see that the number of ways of choosing AA or DD to color from each of n2n^2 blocks is the same as the number of choosing nn distinct integers lying in between 11 and 2n2n (11 and 2n2n inclusive), which equals 2nCn2nC_n. The same argument applies to the number of ways of choosing BB or CC to color, and therefore, the total number of coloring the 2n22n^2 squares of the original grid to satisfy the condition of the problem is (2nCn)2(2nC_n)^2.

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 and solution reproduced as published; topic and difficulty added by this site.