A calendar is a (finite) rectangular grid. A calendar is valid if it satisfies the following conditions: (i) Each square of the calendar is colored white or red, and there are exactly 10 red squares. (ii) Suppose that there are $N$ columns of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the top row to the bottom row, and within each row from left to right, there do not exist $N$ consecutive numbers such that the squares they are in are all white. (iii) Suppose that there are $M$ rows of squares in the calendar. Then if we fill in the numbers $1,2,\ldots$ from the left-most column to the right-most column, and within each column from bottom to top, there do not exist $M$ consecutive numbers such that the squares they are in are all white. In other words, if we rotate the calendar clockwise by $90^{\circ}$, the resulting calendar still satisfies (ii). How many different kinds of valid calendars are there? (Remark: During the actual exam, the contestants were confused about what counts as different calendars. So although this was not in the actual exam, I would like to specify that two calendars are considered different if they have different side lengths or if the $10$ red squares are at different locations.)
Problem
Source: 2018 Taiwan TST Round 3
Tags: combinatorics, Taiwan
USJL
04.04.2020 16:26
I think this one is really interesting, so I'm just going to sneak in the answer here, and maybe someone could figure out the proof and post it here
$10!$.
62861
04.04.2020 19:05
This is hard to explain without a lot of diagrams...
The answer is $10!$.
Say two calendars are equivalent if we can go from one to the other by applying the following type of operation, or its $90^\circ$ rotation, where the $\times$s denote white cells:
Say a calendar is standard if it is $10 \times 10$, with one red cell in each row and column. The main claim is the following:
Key Idea. Every valid calendar is equivalent to exactly one standard calendar, and vice-versa.
Now, we work towards proving the above.
Claim. No two standard calendars are equivalent.
Proof. Given a calendar, consider the row numbering of its $10$ red squares by labeling its red squares $1,\ \dots,\ 10$ from the top row to the bottom row, going from left to right in each row. Similarly, define its column numbering as the labeling of its $10$ red squares by labeling its red squares $1,\ \dots,\ 10$ from the left column to the right column, going from bottom to top in each column.
The key insight is that the row and column numberings of the red squares are preserved under both types of moves, so by fixing the row numbering and then looking at the order of red cells under the column ordering, we obtain that each calendar has a signature: a permutation on $\{1, \dots, 10\}$ invariant under moves. Since the $10!$ standard configurations have different signatures, no two are equivalent.
Claim. Every valid calendar is equivalent to a standard calendar.
Proof. Apply row expansion moves to separate pairs of red cells in the same row; do similarly for pairs of red cells in the same column. This won't introduce any all-white rows or columns, but just to be safe, we can then delete all-white rows and columns to reach a standard calendar.
Claim. Every standard calendar is equivalent to exactly one valid calendar.
Proof. Clearly every standard calendar is equivalent to at least one valid calendar (apply removal moves until no longer possible), so we'll show that there is at most one valid calendar for each signature $\pi$.
First, we claim that the number of columns in such a valid calendar equals the number of ascents $\alpha$ of $\pi$; i.e. the number of $i$ with $\pi(i) < \pi(i+1)$.
To see at least this many columns are required, note that from bottom to top, the red cell labels encountered in a column are decreasing. Hence each ascent must start a new column.
Now suppose that a calendar with signature $\pi$ has more than $\alpha$ ascents. Then there is a non-ascent $(\pi(i), \pi(i+1))$ which starts a new column. In this case, we can use a column removal move to bring $\pi(i)$ and $\pi(i+1)$ one column closer together, so this calendar was not valid.
As a corollary, this tells us that in a valid calendar with signature $\pi$, the red cell labeled $i$ must be in the $s^\text{th}$ column, where $i$ is part of the $s^\text{th}$ increasing contiguous subsequence of the permutation $\pi$.
In particular, we know the correct column for every red cell. By applying similar analysis, we know the correct row for every red cell, and thus the valid calendar is unique.
USJL
05.04.2020 10:47
CantonMathGuy wrote: This is hard to explain without a lot of diagrams...
The answer is $10!$.
Say two calendars are equivalent if we can go from one to the other by applying the following type of operation, or its $90^\circ$ rotation, where the $\times$s denote white cells:
Say a calendar is standard if it is $10 \times 10$, with one red cell in each row and column. The main claim is the following:
Key Idea. Every valid calendar is equivalent to exactly one standard calendar, and vice-versa.
Now, we work towards proving the above.
Claim. No two standard calendars are equivalent.
Proof. Given a calendar, consider the row numbering of its $10$ red squares by labeling its red squares $1,\ \dots,\ 10$ from the top row to the bottom row, going from left to right in each row. Similarly, define its column numbering as the labeling of its $10$ red squares by labeling its red squares $1,\ \dots,\ 10$ from the left column to the right column, going from bottom to top in each column.
The key insight is that the row and column numberings of the red squares are preserved under both types of moves, so by fixing the row numbering and then looking at the order of red cells under the column ordering, we obtain that each calendar has a signature: a permutation on $\{1, \dots, 10\}$ invariant under moves. Since the $10!$ standard configurations have different signatures, no two are equivalent.
Claim. Every valid calendar is equivalent to a standard calendar.
Proof. Apply row expansion moves to separate pairs of red cells in the same row; do similarly for pairs of red cells in the same column. This won't introduce any all-white rows or columns, but just to be safe, we can then delete all-white rows and columns to reach a standard calendar.
Claim. Every standard calendar is equivalent to exactly one valid calendar.
Proof. Clearly every standard calendar is equivalent to at least one valid calendar (apply removal moves until no longer possible), so we'll show that there is at most one valid calendar for each signature $\pi$.
First, we claim that the number of columns in such a valid calendar equals the number of ascents $\alpha$ of $\pi$; i.e. the number of $i$ with $\pi(i) < \pi(i+1)$.
To see at least this many columns are required, note that from bottom to top, the red cell labels encountered in a column are decreasing. Hence each ascent must start a new column.
Now suppose that a calendar with signature $\pi$ has more than $\alpha$ ascents. Then there is a non-ascent $(\pi(i), \pi(i+1))$ which starts a new column. In this case, we can use a column removal move to bring $\pi(i)$ and $\pi(i+1)$ one column closer together, so this calendar was not valid.
As a corollary, this tells us that in a valid calendar with signature $\pi$, the red cell labeled $i$ must be in the $s^\text{th}$ column, where $i$ is part of the $s^\text{th}$ increasing contiguous subsequence of the permutation $\pi$.
In particular, we know the correct column for every red cell. By applying similar analysis, we know the correct row for every red cell, and thus the valid calendar is unique.
That is why I don't want to post a solution myself yet XD nice solution though!