Q47 Matemática  (IMO Shortlist 2004)

Para uma matriz $n\times n$ $A$, seja $X_i$ o conjunto de entradas na linha $i$ e $Y_j$ o conjunto de entradas na coluna $j$, $1\le i,j\le n$. Dizemos que $A$ é ouro se $X_1,\dots ,X_n,Y_1,\dots ,Y_n$ são conjuntos distintos. Encontre o menor inteiro $n$ tal que exista uma matriz dourada $2004\times 2004$ com entradas no conjunto $\{1,2,\dots ,n\}$.