Berkeley Math Circle

Solution:

The $1 \times 1$ matrix whose only entry is $1$ is certainly golden; we claim there are no others. To see this, note that each of the numbers $1,2, \ldots, 2 n-1$ must appear at least $n$ times in the matrix. (Proof: Suppose some number $k$ appears less than $n$ times. Because there are $n$ columns, some column does not contain $k$. Likewise, some row does not contain $k$; then the union of this row and this column fails to contain $k$, contrary to the given). So we have at least $n(2 n-1)$ entries in the matrix. But an $n \times n$ matrix has $n^{2}$ entries, so $n^{2} \geq n(2 n-1) \Rightarrow n \geq 2 n-1 \Rightarrow 1 \geq n$, and only the $1 \times 1$ matrix can be golden.

Solution:

As before, the $1 \times 1$ matrix consisting only of a $1$ is golden. Now, note that the union of any row and any column in an $n \times n$ golden matrix contains exactly $2 n-1$ entries, so each of the numbers $1,2, \ldots, 2 n-1$ must appear exactly once in this union. Therefore, there is no room in the matrix for any numbers other than $1,2, \ldots, 2 n-1$. Moreover, if any of these entries appeared twice, say once at the intersection of the $i$th row and $j$th column and once at the $i'$th row and $j'$th column, then the union of the $i$th row and $j'$th column would contain this number twice, not leaving enough room for the remaining $2 n-2$ numbers. So each number can appear only once in the matrix, meaning it can have only $2 n-1$ entries. Thus $n^{2}=2 n-1 \Rightarrow n^{2}-2 n+1=0 \Rightarrow n=1$, and only the $1 \times 1$ matrix is golden.