13. C6 (IRN) For an $n \times n$ matrix $A$, let $X_{i}$ be the set of entries in row $i$, and $Y_{j}$ the set of entries in column $j, 1 \leq i, j \leq n$. We say that $A$ is golden if $X_{1}, \ldots, X_{n}, Y_{1}, \ldots, Y_{n}$ are distinct sets. Find the least integer $n$ such that there exists a $2004 \times 2004$ golden matrix with entries in the set $\{1,2, \ldots, n\}$.
13. Since $X_{i}, Y_{i}, i=1, \ldots, 2004$, are 4008 distinct subsets of the set $S_{n}=$ $\{1,2, \ldots, n\}$, it follows that $2^{n} \geq 4008$, i.e $n \geq 12$.
Suppose $n=12$. Let $\mathcal{X}=\left\{X_{1}, \ldots, X_{2004}\right\}, \bar{Y}=\left\{Y_{1}, \ldots, Y_{2004}\right\}, \mathcal{A}=$ $\mathcal{X} \cup \mathcal{Y}$. Exactly $2^{12}-4008=88$ subsets of $S_{n}$ do not occur in $\mathcal{A}$.
Since each row intersects each column, we have $X_{i} \cap Y_{j} \neq \rrbracket$ for all $i, j$. Suppose $\left|X_{i}\right|,\left|Y_{j}\right| \leq 3$ for some indices $i, j$. Since then $\left|X_{i} \cup Y_{j}\right| \leq 5$, any of at least $2^{7}>88$ subsets of $S_{n} \backslash\left(X_{i} \cap Y_{j}\right)$ can occur in neither $\mathcal{X}^{\prime}$ nor $\mathcal{Y}$, which is impossible. Hence either in $\mathcal{X}$ or in $Y$ all subsets are of size at least 4. Suppose w.lo.g. that $k=\left|X_{l}\right|=\min _{i}\left|X_{i}\right| \geq 4$. There are
$$
n_{k}=\binom{12-k}{0}+\binom{12-k}{1}+\cdots+\binom{12-k}{k-1}
$$
subsets of $S \backslash X_{t}$ with fewer than $k$ elements, and none of them can be either in $\mathcal{X}$ (because $\left|X_{l}\right|$ is minimal in $\mathcal{X}^{\prime}$ ) or in $\mathcal{Y}$. Hence we must have $n_{k} \leq 88$. Since $n_{4}=93$ and $n_{5}=99$, it follows that $k \geq 6$. But then none of the $\binom{12}{1}+\cdots+\binom{12}{5}=1586$ subsets of $S_{n}$ is in $\mathcal{X}$, hence at least $1586-88=1498$ of them are in $Y$. The 1498 complements of these subsets
also do not occur in $\mathcal{X}$, which adds to 3084 subsets of $S_{n}$ not occurring in $\mathcal{X}$. This is clearly a contradiction.
Now we construct a golden matrix for $n=13$. Let
$$
A_{1}=\left[\begin{array}{ll}
1 & 1 \\
2 & 3
\end{array}\right] \text { and } A_{m}=\left[\begin{array}{ll}
A_{m-1} & A_{m-1} \\
A_{m-1} & B_{m-1}
\end{array}\right] \text { for } m=2,3, \ldots \text {. }
$$
where $B_{m-1}$ is the $2^{m-1} \times 2^{m-1}$ matrix with all entries equal to $m+2$. It can be easily proved by induction that each of the matrices $A_{m}$ is golden. Moreover, every upper-left square submatrix of $A_{m}$ of size greater than $2^{m-1}$ is also golden. Since $2^{10}<2004<2^{11}$, we thus obtain a golden matrix of size 2004 with entries in $S_{13}$.