12 Let $A$ be an $m \times m$ matrix. Let $X_{i}$ be the set of entries in the $i$th row and $Y_{j}$ the set of entries in the $j$th column, $1 \leq i, j \leq m$. $A$ is called cool if the sets $X_{1}, \ldots, X_{m}, Y_{1}, \ldots, Y_{m}$ are all different. Determine the smallest value for $n$ so that a cool $2005 \times 2005$ matrix with entries from the set $\{1,2, \ldots, n\}$ exists.

## Solution
Let $\mathcal{X}$ be the set of $X_{i}$ and $\mathcal{Y}$ the set of $Y_{j}$. It must hold $2^{n} \geq|\mathcal{X} \cup \mathcal{Y}|=2 \cdot 2005$, i.e. $n \geq 12$. Assume $n=12$ would be possible. Exactly $2^{12}-2 \cdot 2005=86$ subsets of $\{1,2, \ldots, 12\}$ are not in $\mathcal{X} \cup \mathcal{Y}$. The central point is the simple observation that every row has a common element with every column:

$$
X_{i} \cap Y_{j} \neq \emptyset, \quad \text { for } 1 \leq i, j \leq 2005
$$

Assume that there are $i, j$, so that $\left|X_{i} \cup Y_{j}\right| \leq 5$ holds. Since every column and every row has a common element with this set, there is no subset of the complement in $\mathcal{X} \cup \mathcal{Y}$. However, there are at least $2^{7}>86$ subsets, contradiction. So the following applies

$$
\left|X_{i} \cup Y_{j}\right| \geq 6, \quad \text { for } 1 \leq i, j \leq 2005
$$

From this it follows that all rows or all columns have at least four different entries, if these are the rows. Set $k=\min \left|X_{i}\right| \geq 4$ and choose $\alpha$ with $\left|X_{\alpha}\right|=k$. Because of (4), no subset of the complement of $X_{\alpha}$ lies in $\mathcal{Y}$. Therefore, by definition of $k$, no subset of the complement of $X_{\alpha}$ with less than $k$ elements lies in $\mathcal{X} \cup \mathcal{Y}$. For $k=4$ these are

$$
\binom{8}{0}+\binom{8}{1}+\binom{8}{2}+\binom{8}{3}=93>86
$$

subsets, for $k=5$ they are

$$
\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}=99>86
$$

Contradiction. Consequently, $k \geq 6$ applies. The number of at most 5-element subsets of $\{1,2, \ldots, 12\}$ is

$$
\binom{12}{0}+\binom{12}{1}+\binom{12}{2}+\binom{12}{3}+\binom{12}{4}+\binom{12}{5}=1586
$$

None of them are in $\mathcal{X}$, and at least $1586-86$ of them are in $\mathcal{Y}$. The complements of these sets have at least 7 elements and are also not in $\mathcal{X}$. Consequently, in $\mathcal{X}$ there are at least

$$
1586+(1586-86)=3086>2^{12}-2005
$$

sets do not exist, a contradiction. Therefore, $n \geq 13$ applies.

We now prove that a cool $2005 \times 2005$-matrix exists for $n=13$. First, we inductively construct a cool $2^{n} \times 2^{n}$ matrix $A_{n}$ with entries from the set $\{1,2, \ldots, n+2\}$. Set

$$
A_{1}=\left(\begin{array}{ll}
1 & 1 \\
2 & 3
\end{array}\right)
$$

and then recursively define

$$
A_{n+1}=\left(\begin{array}{cc}
A_{n} & A_{n} \\
A_{n} & B_{n}
\end{array}\right)
$$

where $B_{n}$ is the $2^{n} \times 2^{n}$ matrix whose entries are all equal to $n+2$. Let $X_{1}, \ldots, X_{2^{n}}$, $Y_{1}, \ldots, Y_{2^{n}}$ be the row and column sets of $A_{n}$ respectively. Then the row sets of $A_{n+1}$ are given by $X_{1}, \ldots, X_{2^{n}}, X_{1} \cup\{n+2\}, \ldots, X_{2^{n}} \cup\{n+2\}$, the column sets by $Y_{1}, \ldots, Y_{2^{n}}, Y_{1} \cup\{n+2\}, \ldots, Y_{2^{n}} \cup\{n+2\}$. With $A_{n}$, $A_{n+1}$ is therefore also cool. Finally, it is easy to see that the upper left $2005 \times 2005$ submatrix of $A_{11}$ is also cool due to the special form of the matrices constructed in this way. This concludes the proof.