Exercise 5. Martin is trying to fill each cell of a rectangular grid with 8 rows and $\mathrm{n}$ columns with one of the four letters $\mathrm{P}, \mathrm{O}, \mathrm{F}$, and $\mathrm{M}$ such that for any pair of distinct rows, there is at most one column where the intersections of the two rows are cells with the same letter. What is the largest integer $n$ for which this is possible?
Solution to Exercise 5 In this problem, we are looking for the largest integer satisfying a certain property. Suppose we want to show that the largest integer sought is the integer c. To show that c is indeed the largest integer, we will on the one hand show that if an integer n satisfies the property, then n ≤ c, and on the other hand we will show that we can find a table with exactly c columns.

The statement provides an assumption about the rows and columns of a table.

We start by looking at the information we have about the rows of this table. There are 8 rows, so there are \(\binom{8}{2} = 28\) pairs of rows.

We then look at the information we have about the columns of the table. Since the statement's hypothesis mentions identical letters within the same column, we will count how many pairs of identical letters can belong to the same column. We fix a column of the table and see how many pairs of identical letters we can form at a minimum. After several trials on a column of size 8, we conjecture that there are always at least 4 pairs of identical letters within the same column. Indeed, in a column there are 8 letters, so a letter appears at least 2 times.

- If each letter appears at most 2 times, then each letter appears exactly 2 times since there are 8 cells in the column and 4 possible letters. We thus have 4 pairs of identical letters in the column.
- If a letter appears exactly 3 times, say the letter P, then we can form 3 pairs of letters P. Among the 5 remaining letters, at least one of the letters O, F, and M appears twice according to the pigeonhole principle, which gives us a fourth pair of identical letters.
- If a letter appears at least 4 times in the column, say the letter P, we can form 4 pairs of letters P.

Thus, in a column, we can always find 4 pairs of identical letters. Therefore, for each column, there are at least 4 pairs of rows such that the intersections with the column have the same letter. But according to the statement's hypothesis, a pair of rows can be associated with at most one column such that its intersections with the two rows are two cells containing the same letter. We deduce that there are at most \(4 \times n\) pairs of rows. Therefore, \(4n \leq 28\) and \(n \leq 7\).

Conversely, there exists a configuration with the following 7 columns:

| P | P | P | P | P | P | P |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| O | O | O | O | O | P | O |
| F | F | F | F | O | O | P |
| M | M | M | M | P | O | O |
| P | M | F | O | F | F | F |
| O | F | M | P | M | F | M |
| F | P | P | M | M | M | F |
| M | O | O | F | F | M | M |

The largest integer \(\mathfrak{n}\) of columns is therefore \(\mathfrak{n} = 7\).

Graders' Comments

The exercise is generally well done; students have understood that the constraint is that each column adds 4 pairs of identical letters, but few have provided a fully rigorous proof of this fact. Some have given a set of 7 columns and justified that 7 is optimal because it is not possible to add a column to what they have done. However, this justification is not sufficient. Indeed, just because the construction cannot be enlarged does not mean that its size is maximal: one can imagine that there exists a larger and very different construction from the one given.