Maths Olympiad Prep

Library / /308 of 397

Combinatorics Difficulty 6.7 National Olympiad Prove it Taiwan

A calendar is a rectangular sheet of grid paper. We say a calendar complies with the regulations if and only if it satisfies the following three conditions:
(1) Every cell of the calendar is colored white or red, and there are exactly 1010 red cells.
(2) If a horizontal row of the calendar has a total of NN cells, then when we fill in 1,2,1, 2, \dots in order starting from the cell in the uppermost-left corner, going from left to right and then from top to bottom, we will not be able to find NN consecutive numbers whose cells are all white.
(3) If a vertical column of the calendar has a total of MM cells, then when we fill in 1,2,1, 2, \dots in order starting from the cell in the lowermost-left corner, going from bottom to top and then from left to right, we will not be able to find MM consecutive numbers whose cells are all white (that is to say, if we rotate the whole calendar 9090 degrees clockwise, it still satisfies condition (2)).
試問有多少種符合法規的月曆? How many calendars comply with the regulations?

A calendar is a rectangular sheet of grid paper. We say a calendar complies with the regulations if and only if it satisfies the following three conditions:
(1) Every cell of the calendar is colored white or red, and there are exactly 1010 red cells.
(2) If a horizontal row of the calendar has a total of NN cells, then when we fill in 1,2,1, 2, \dots in order starting from the cell in the uppermost-left corner, going from left to right and then from top to bottom, we will not be able to find NN consecutive numbers whose cells are all white.
(3) If a vertical column of the calendar has a total of MM cells, then when we fill in 1,2,1, 2, \dots in order starting from the cell in the lowermost-left corner, going from bottom to top and then from left to right, we will not be able to find MM consecutive numbers whose cells are all white (that is to say, if we rotate the whole calendar 9090^\circ clockwise, it still satisfies condition (2)).
How many calendars comply with the regulations?

Solution

Answer: 10!=362880010! = 3628800 ways.
Note that in a 10×1010 \times 10 grid, the number of ways to color 1010 cells red so that each row and each column has exactly one red cell is 10!10!. Below we establish a bijection between such colorings of the 10×1010 \times 10 grid and calendars that comply with the regulations.

Figure 1

– Grid \rightarrow calendar complying with the regulations:
As in the figure above, perform the following operations:

1. First look at two adjacent rows; if the red cell in the left row is higher than the red cell in the right row, then bold the grid line between the two rows.
2. Next look at two adjacent columns; if the red cell in the upper column is to the right of the red cell in the lower column, then bold the grid line between the two columns.
3. Erase all the bolded grid lines, and we obtain a calendar that complies with the regulations:

(Proof)
* First we prove that after erasing, the result is a calendar. Note that within each region separated out by the bold grid lines, there is at most one red cell; this is because if there were two, then if the relative positions of the two red cells are upper-left and lower-right, there must still be a bold vertical line between them, and if they are lower-left and upper-right, there must still be a bold horizontal line between them, and in either case this is a contradiction. This guarantees that after erasing the thin grid lines, the result must be a calendar.
* Next we prove that it complies with the regulations. Condition (1) is obviously satisfied. If condition (2) were violated, this would mean that in the original grid there must be a bold horizontal line such that the red cells in the row above it are all to the left of the red cells in the row below it, but this contradicts the very construction of the bold horizontal line itself. Condition (3) follows similarly.

### - Calendar complying with the regulations \rightarrow grid:
For each cell in the calendar, perform the following actions in order:

1. Suppose there are pp red cells in the same row as this cell, and qq red cells in the same column, then subdivide this cell further into q×pq \times p smaller cells.
2. If this cell is red, and it is the rr-th red cell counting from the top in its row, and the rr-th small cell counting from the left in its column, then among the subdivided smaller cells, color red the cell in the rr-th row counting from the bottom and the ss-th column counting from the left, leaving the rest white.

It is easy to see that the above constitutes the inverse map of the mapping in the first part.

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 translated into English from zh; metadata (topic, difficulty) added by this project.