IMO Shortlist 2004 problem C6
Dodao/la:
arhiva2. travnja 2012. For an
![{n\times n}](/media/m/b/7/3/b732a333e24f574ebc55a036296f8c67.png)
matrix
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
, let
![X_{i}](/media/m/c/f/d/cfdb9bb7978a548e2f94c9e9348f2bb7.png)
be the set of entries in row
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
, and
![Y_{j}](/media/m/2/4/e/24e70673e36ee1dc45d8e622ec278ce3.png)
the set of entries in column
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
,
![{1\leq i,j\leq n}](/media/m/b/f/1/bf14378df6fc97879dd92b362faafeb7.png)
. We say that
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
is golden if
![{X_{1},\dots ,X_{n},Y_{1},\dots ,Y_{n}}](/media/m/9/0/c/90c637a9b7d7a8d0d3c98d5cc850a349.png)
are distinct sets. Find the least integer
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
such that there exists a
![{2004\times 2004}](/media/m/1/0/6/1060ef66ff3ba0528686ad26c606e980.png)
golden matrix with entries in the set
![{\{1,2,\dots ,n\}}](/media/m/5/2/6/52692573c84bb5cfac45bca1d838cd00.png)
.
%V0
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},\dots ,X_{n},Y_{1},\dots ,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,\dots ,n\}}$.
Izvor: Međunarodna matematička olimpijada, shortlist 2004