Track / Stage 6 / 163 of 400 #1163 of 1964

Problem 1163

National olympiad, first round

Combinatorics Difficulty 6.2 Find the answer

A [i]calendar[/i] is a (finite) rectangular grid. A calendar is [i]valid[/i] 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.)

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Official solution

To solve this problem, we need to determine the number of valid calendars that satisfy the given conditions. Let's break down the problem step by step.

1. Understanding the Grid and Coloring:
- The calendar is a rectangular grid with $M$ rows and $N$ columns.
- Each square in the grid is either white or red.
- There are exactly 10 red squares in the grid.

2. **Condition (ii) - No $N$ Consecutive White Squares in Rows:**
- When filling the numbers $1, 2, \ldots$ from the top row to the bottom row and within each row from left to right, there should not be $N$ consecutive white squares.

3. **Condition (iii) - No $M$ Consecutive White Squares in Columns:**
- When filling the numbers $1, 2, \ldots$ from the left-most column to the right-most column and within each column from bottom to top, there should not be $M$ consecutive white squares.
- This condition is equivalent to rotating the calendar 90 degrees and applying condition (ii).

4. Counting Valid Calendars:
- We need to count the number of ways to place 10 red squares in the grid such that both conditions (ii) and (iii) are satisfied.

5. Permutations of Red Squares:
- Since the problem states that two calendars are considered different if the 10 red squares are at different locations, we need to consider the permutations of the 10 red squares.
- The number of ways to arrange 10 red squares in a grid is given by the number of permutations of 10 items, which is $10!$ .

6. Verification of Conditions:
- We need to ensure that the placement of the 10 red squares satisfies both conditions (ii) and (iii). However, the problem does not provide specific constraints on the dimensions $M$ and $N$ of the grid.
- Given the lack of specific constraints, we assume that the placement of 10 red squares in any configuration that avoids $N$ consecutive white squares in rows and $M$ consecutive white squares in columns is valid.

Therefore, the number of different kinds of valid calendars is given by the number of permutations of the 10 red squares.

The final answer is $\boxed{ 10! }$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.