Can they be multisets? I mean, can we repeat elements in the same column and row? or must they be distinct?, and if we can repeat them, what equality condition should we use???

That's problem 3 of the 2nd German TST 2005. I guess it's from the ISL 2005. LaTeX writeup: For an $n\times n$ matrix A, let $X_i$ be the set of all entries in the row i, and $Y_j$ be the set of all entries in the column j. We call the matrix A a golden matrix if all sets $X_1$, $X_2$, ..., $X_n$, $Y_1$, $Y_2$, ..., $Y_n$ are pairwisely distinct. Find the smallest integer N such that there exists a golden $2004\times 2004$ matrix whose entries are numbers from the set {1; 2; ...; N}. As for Pascual's question, two entries in a row or in a column can be equal, but the sets are sets, not multisets, so that equal elements are counted only once (hence, not all of the sets $X_1$, $X_2$, ..., $X_n$, $Y_1$, $Y_2$, ..., $Y_n$ must necessarily have 2005 elements), and two such sets are equal if they are equal as sets (just take the formal point of view). In our test, the greatest score for this problem were 4 marks. When we were told the solution, I tried to follow at the beginning, but then I fell asleep since it was just too ugly and boring... darij

Thanks You can post one complete solution? ;/

$n +1$?

ooppps i am very sorry but now i am starting to believe that the answer will be $(log_2 n)+2$. It is easy to prove one needs at least that, because there are $2^m$ subsets of $(1,2,3,4...,m)$. The only hard case is when $n$ is a power of $2$. For example when $n=2^t$, we need $t+2$ objects instead of $t+1$, because if it were possible with $t+1$, then all subsets should be in some row or some column, so there would be a row with $1,1,1.....,1$, but since there are only $2^t$ subsets containing $1$, there will be also a column with $1,1,1...,1$ (simple piggeonholes). Until now, i proved that $f(2n)=f(n)+1$, we only have to prove left that: $f(2n+1)=f(n)+1$, and we will be done! $f(n)$ is the minimun number!

Does someone knows a solution???? Until now i have found $f(2)=3$, $f(3)=4$, $f(n+1)\leq f(n)+1$, $f(2^n)=n+2$, $f(6)=5$. I want to prove that we always have $f(3.2^n)=n+4$ it is clearly enough to prove it for arbitrry increasing sequence of $n$. I think also one could prove that $f$ is monotonically increasing. I also think $f(2n+1)\leq f(n)+1$ (not proved) and $f(2n)\leq f(n)+1$ (already proved) if one proves this facts the answer then will easily follows.

pascual, try to prove $f(2004)=13$ directly. actually, you showed that $12\leq f(2004)\leq 13$ already. now, it is some work to exclude the case $f(2004)=12$, but this can be done by considering some tons of cases - in the TST, i still had 2 or 3 hours for this step and couldn't succeed, but it is quite clear that $f(2004)>12$ since 2004 is quite near to the next power of 2, 2048. our delegation leader than gave a complete proof to us, but i can't really remember it. maybe i will try to reconstruct the proof if you really want me to.

Yes,we want,reconstruct please.

Solution- I will only show that $n=12$ is not possible. My construction for $13$ is too hard to put into words. So if possible let $A$ be a golden $2004\times 2004$ matrix with entries in $\{1,2,\cdots,12\}$. Let the row sets and the column sets be $X_1,X_2,\cdots X_{2004}$ and $Y_1,Y_2,\cdots,Y_{2004}$ respectively and let $\mathbb{H}=\{X_1,X_2,\cdots X_{2004}, Y_1,Y_2,\cdots,Y_{2004}\}$ Observation - $X_i^c\cap Y_j^c\notin \mathbb{H}$ For if it was a $Y_k$ then it must have a element in common with $X_i$ and similar for other case. Now total number of subsets of $\{1,2,\cdots,12\}$ are $4096$ and hence if no subset in $\mathbb{H}$ had three elements we would have $4008=|\mathbb{H}|\leq 4096$- $ {12}\choose {3}$$=3876$, a contradiction. Hence there is atleast one subset having exactly three elements . WLOG let it be $X_1=\{1,2,3\}$. Now for each $1\leq i\leq 2004$ define $f(Y_i)=Y_i^c\cap X_1^c$. Note that $f(Y_i)\notin\mathbb{H} $ by observation. For some $i$ let $S=\{Y_j| f(Y_i)=f(Y_j)\}$ we claim that $|S| \leq 7$ From this we have that the set $\{f(Y_i)| 1\leq i\leq 2004\}$ will have atleast $\frac{2004}{7}$ elements . Hence we would have atleast $286$ sets which are not part of $\mathbb{H}$, but this is a contradiction as $4096-4008=88<286$ Hence we only need to show that $|S|\leq 7$, for this consider a given set $B$ in the image of $f$. To get corresponding $Y_i$ we can add any of $\{\phi\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}$ to $B$ and then take it's complement, and note that these are the only possible ways and there are $7$ possibilities. Hence proved.

The answer is $n=13$. We shall call a golden matrix with entries from $\{1,2,...,k\}$ a $k$-golden matrix. We will first show that there exists a $13$-golden matrix. We will do so by proving the following claim: CLAIM 1. Let $p,q$ be integers such that $p<q\leq 2p$, suppose there exists a $p\times p$ $k-$ golden matrix, then there exists a $q\times q$ $(k+1)-$golden matrix. Proof. Let $A$ be the $p\times p$ $k-$ golden matrix, let $q=p+m$ where $m\leq p$. Let $B$ be the matrix formed by the first $m$ columns of $A$, and let $C$ be the matrix formed by the first $m$ rows of $A$. Let $D$ be the $m\times m$ matrix with all entries being $n+1$, then it is straightforward to check that the block matrix $$\begin{pmatrix} A&B\\ C&D \end{pmatrix}$$is a $q\times q$ $(k+1)-$golden matrix. $\blacksquare$ Now $\begin{pmatrix} 1&1\\2&3\end{pmatrix}$ is a $2\times 2$ $3$-golden matrix. Consider the sequence $$(a_1,...,a_{11})=(2,4,8,16,32,63,126,251,501,1002,2004)$$By the CLAIM 1 there exist a $a_i\times a_i$ $(i+2)-$golden matrix. This proves the existence of a $2004\times 2004$ $13$-golden matrix. Now we show that there does not exists a $2004\times 2004$ $12-$ golden matrix. Suppose on the contrary that such matrix exists. Let $S=\{1,2,...,12\}$. Let $S_i$ be the family of subsets of $S$ with $i$ elements. Let $X=X_1\cup...\cup X_{2004}$, define $Y$ similarly and let $E=X\cup Y$. Notice that for each $i,j$ we have $X_i\cup Y_j\neq \emptyset$. Let $F=2^S\setminus E$ CLAIM 2. (i) $|F\cup S_0|=1$ (ii) $|F\cup S_1|\geq 11$ (iii) $|F\cup S_2|\geq 36$ Proof. (i) is obvious since the only element in $S_0$ is the emptyset, which does not belong to $E$. Now suppose on the contrary that $|F\cup S_1|\geq 2$, WLOG assume $\{1\},\{2\}\in E$, notice that they must both belong to either $X$ or $Y$. Suppose they belong to $X$, then there are only $2^{10}=1024$ elements in $2^S$ which are not disjoint with both of them, hence there are only $1024$ possibilities for elements in $Y$, contradicting the fact that $|Y|=2004$. This proves $(ii)$ Now suppose on the contrary that $F|\cup S_2|\leq 35$, WLOG assume $\{1,2\}\in X$, if none of the $2$ element subsets of $\{3,4,...,12\}$ are in $E$ then we are done, hence assume $\{3,4\}\in X$. If all of the 2 element subsets of $\{5,6,...,12\}$ are in $F$ then we are done, hence assume $\{5,6\}\in X$. Now by inclusion-exclusion principle, there are exactly $$3\times 2^{10}-3\times 2^8+2^6=2368$$elements of $2^S$ which are disjoint to at least one of $\{1,2\},\{3,4\}$ and $\{5,6\}$. Therefore all of them can't be in $Y$. Therefore there are only $4096-2368=1728$ possibilities for $Y$, contradiction. $\blacksquare$ Now we further divide into two cases CASE I: $S_2\cup E\neq \emptyset$ WLOG assume $\{1,2\}\in X$ CLAIM 3: For each $i=3,4,5,6$ we have $S_i\cup Y=\emptyset$ Proof. Suppose there exists $A\in S_3\cup Y$. Since $|A\cap \{1,2\}|\geq 1$ we have $|A\cup \{1,2\}|\leq 4$, hence $|S\setminus (A\cup \{1,2\})|\geq 8$. Let $Z=S\setminus(A\cup \{1,2\})$, for each subset of $Z$, it is disjoint to both $A$ and $\{1,2\}$, hence it can't be in $E$, therefore $|F|\geq 256$, $|E|\leq 4096-256<2\times 2004$, contradiction. For similar reasoning we have $S_4\cup Y=\emptyset$. Now suppose $A\in S_5\cup Y$, let $B=S\setminus A$ then consider all the 3 and 4 element subsets of $B$, they do not belong to $X$ since they are disjoint with $A$, they also do not belong to $Y$ since $S_3\cup Y= S_4\cup Y=\emptyset$, hence they belong to $F$, therefore, $$|F|\geq 1+11+36+\binom{7}{3}+\binom{7}{4}>4096-2\times 2004=88$$contradiction. For $i=6$, we can use the similar reasoning to obtain $$|F|\geq 1+11+36+\binom{6}{3}+\binom{6}{4}+\binom{6}{5}=89$$contradiction. $\blacksquare$ Hence there are at most $4096-\sum_{i=3}^6\binom{12}{i}=1665$ sets in $Y$, contradiction. CASE II: $S_2\cup E=\emptyset$ If $S_3\cup E=\emptyset$ then we are done. Now assume $\{1,2,3\}\in X$, using the same reasoning we have $S_3\cup Y=\emptyset$ If $S_4\cup Y=\emptyset$, then $|F|\geq 1+11+\binom{12}{2}+\binom{8}{3}>88$, contradiction. Similarly $S_5\cup Y=S_6\cup Y=\emptyset$, using the exact reasoning as in CASE I we obtain a contradiction. This completes the proof.