we named a $n*n$ table $selfish$ if we number the row and column with $0,1,2,3,...,n-1$.(from left to right an from up to down) for every {$ i,j\in{0,1,2,...,n-1}$} the number of cell $(i,j)$ is equal to the number of number $i$ in the row $j$. for example we have such table for $n=5$ 1 0 3 3 4 1 3 2 1 1 0 1 0 1 0 2 1 0 0 0 1 0 0 0 0 prove that for $n>5$ there is no $selfish$ table
Problem
Source: iran tst 2014 first exam
Tags: LaTeX, combinatorics unsolved, combinatorics
nima1376
15.04.2014 20:03
it is my friend ideas
1- we have prove we can not Fill row 0
2-sum of number in row 0 is n
3- now it is easy by give some case
sg1997
19.04.2014 17:52
first prove that each no has to appear in the table. else there would be a row of n 0's which is not possible. let x_i be the no of times i appears i=0(1)n-1 hence sum (x_i) = n^2 (sum of each column is n as is evident) i=0(1)n-1 also sum (ix_i) = n^2 from here x_0 = sum ((i-1)x_i) i=2(1)n-1 now x_i>=1 for all i also for all j there exists an x_i such that x_i>=j note that if x_i.= 2 for each i>= 2 then x_0 >= n^2 -2n +3 for n>5 (note that there must exist one row where 0 does not occur) hence there exists a row of n zeroes thats a contra! if x_i =1 for some i>=2 then let A be the no of those i's such that x_i=1 (i>=2) then prove that no of n-1 is at least A hence sum ((i-1)x_i) i=2(1)n-1 increases further and clearly thats inadmissible sorry i dont know latex
Aran_mhdn
21.04.2014 21:01
we solved it in mr.saqafians class!last week!
Sniped_Idea
27.02.2018 07:14
No ideas for this problems?
Sniped_Idea
06.07.2018 17:03
Bumping this Full solutions plz !
ThE-dArK-lOrD
27.07.2018 15:58
I think the original problem asked to find all such $n\times n$ tables. Anyway, here's the official solution up to the conclusion that $n\leqslant 5$: Step 1: $a_{0,0}>0$.
If $a_{0,0}=0$, then the number of $0$'s of row zero must be zero, but $a_{0,0}$ is itself zero, which is a contradiction.
Step 2: For each $0\leqslant i\leqslant n-1$, $c_i\leqslant n$.
$$c_i=\sum_{j=0}^{n-1}{a_{j,i}} =\sum_{j=0}^{n-1}(\text{number of }j'\text{s of row }i)\leqslant n.$$
Corollary 1: Let $S$ be the sum of the entries of the table. We have $S\leqslant n^2$. Step 3: There is no $0\leqslant i,j\leqslant n-1$ such that $a_{i,j}\geqslant n$.
By definition, $a_{i,j}\leqslant n$ for each $0\leqslant i,j\leqslant n-1$ (Since $a_{i,j}$ is the number of $i$'s of row $j$). Assume that there exists an entry equal to $n$ (let it be $a_{i,j}$). So all of the entries of row $j$ must be $i$ and $n\geqslant c_j\geqslant a_{i,j}+a_{j,j}=n+i$, so $i=0$ and $a_{0,j}=n$. Since $c_j\leqslant n$ and $a_{1,j}=a_{2,j}=...=a_{n-1,j}=0$, for each $1\leqslant k\leqslant n-1$, row $k$ contains at least one $0$ entry. Hence, $a_{0,i}>0$ for each $1\leqslant i\leqslant n-1$. By step 1, $a_{0,0}>0$ and so all the entries of row $0$ are positive, which is a contradiction.
Step 4: $c_i=n$ for each $0\leqslant i\leqslant n-1$ and consequently, $S=n^2$.
Since all the entries of the table are natural numbers between $0$ and $n-1$, we have
$$c_i=\sum_{j=0}^{n-1}{a_{j,i}}=\sum_{j=0}^{n-1}{(\text{number of }j'\text{s of row }i)}=\text{all the entries of row }i=n.$$
Step 5: $a_{0,0}=1$.
Assume to the contrary that $a_{0,0}\geqslant 2$. So row $0$ contains at least two $0$ entries (say $a_{0,i_1}=a_{0,i_2}=0$). So rows $i_1$ and $i_2$ do not have any $0$ entry and all their entries are positive, thus for each $1\leqslant j\leqslant n-1$, $a_{i_1,j}\geqslant 1$ and $a_{i_2,j}\geqslant 1$. It means that row $j$ contains entries $i_1$ and $i_2$, so for each $0\leq j\leq n-1$, $r_j\geqslant i_1+i_2$. Because $r_j$ is equal to the number of $j$'s in the table, $S\geqslant \sum_{j=0}^{n-1}{(i_1+i_2)j}$. Hence,
$$n^2=S\geqslant \sum_{j=0}^{n-1}{(i_1+i_2)j} \geqslant (1+2)\sum_{j=0}^{n-1}{j}=3\frac{n(n-1)}{2}\implies n\leqslant 3.$$If $n=2$, then number $2$ cannot appear in the table (by step 3) and if $n=3$, then we must complete table $1$ with entries equal to $1$ or $2$. So row $0$ must contain at least a $1$ entry, which is a contradiction.
\begin{tabular}{ | l | c | r |}
\hline
2 & 0 & 0 \\ \hline
& & \\ \hline
& & \\
\hline
\end{tabular}$$\text{Table 1}$$
Step 6: $a_{0,1}=0$ and $a_{0,i}>0$.
If $i\geqslant 3$, a method like that of step 5 leads to a contradiction (if $n=3$, we do not have $a_{0,3}$ in the table).
If $a_{0,2}=0$, then all the entries of row $2$ are positive. So each row contains at least one entry equal to $2$ and so each number $0\leqslant j\leqslant n-1$ has appeared in the table at least $2$ times. Since row $2$ contains at least one entry equal to $2$, we deduce that $r_2\geqslant n+1$. Therefore, $2$ has appeared in the table at least $n+1$ times. Hence
$$n^2=S\geqslant 2(\sum_{j\neq 2}{j})+2(n+1)=n^2+n-2\implies n\leq 2.$$But $2\times 2$ and $1\times 1$ tables do not contain entry $a_{0,2}$. So we have proved that $a_{0,2}>0$ and $a_{0,1}=0$.
Step 7: $r_1\geqslant 2n-2$.
By step $6$, all the entries of row $1$ are positive. Suppose that $a_{1,1}=t$. If $t=1$, then other entries of row $1$ must be at least $2$ and so $r_1\geqslant 2n-1$. If $t>1$, then row $1$ contains at least one entry equal to $t$, $t$ entries equal to $1$ and other entries are at least $2$, so $r_1\geqslant 1\times t+t\times 1+2\times (n-t-1)=2n-2$.
Step 8: $r_0+(r_2+\cdots + r_{n-1})\geqslant n^2-2n+1$.
$r_0$ is the number of $0$'s of the table. Since row zero contains exactly one entry equal to $0$ and all of the entries of row $1$ are positive, the number of $0$'s in rows $2,3,...,n-1$ is equal to $r_0-1$ and thus $n(n-2)-(r_0-1)$ entries of these rows are positive. Hence,
$$r_2+\cdots +r_{n-1}\geqslant n(n-2)-(r_0-1)\implies r_0+(r_2+\cdots +r_{n-1})\geqslant n^2-2n+1.$$
Summing the expressions obtained in steps 7 and 8, we get $$n^2=S=r_0+r_1+\cdots r_{n-1}\geqslant n^2-1.$$ Corollary 2: $r_1=2n-1$ or $2n-2$. Corollary 3: Rows $2,3,...,n-1$ do not contain any $3$'s and at most one of the entries of these rows can be $2$. Therefore, $a_{i,j}=0$ for each $i\geqslant 3,j\geqslant 2$ and $a_{2,2}+a_{2,3}+\cdots a_{2,n-1}\leqslant 1$. Corollary 4: By corollary 3, there are at least $n-2$ entries equal to $0$ in row $j$. So $a_{0,j}=n-2$ or $n-1$. Step 9: $n\leqslant 5$.
By corollary 4, the number of entries in row $0$ equal to $n-1$ or $n-2$ is at least $n-3$, so $a_{n-2,0}+a_{n-1,0}\geqslant n-3$. On the other hand, by corollary 3, at most one of $a_{n-1,0}$ and $a_{n-2,0}$ is $2$. Therefore, $a_{n-2,0}+a_{n-1,0}\leqslant 3$, thus $n-3\leqslant 3$ and so $n\leqslant 6$.
But if $n=6$, by corollary 3, $a_{2,2}+a_{2,3}+a_{2,4}+a_{2,5}\leqslant 1$, hence at most one of them can be nonzero and so $a_{0,2}\geqslant 3$. Therefore, row $0$ does not have any $2$'s and so $a_{2,0}=0$. Consequently, $a_{0,2}\geqslant 4$. On the other hand, $a_{0,3},a_{0,4},a_{0,5}\geqslant 4$. So four entries of row $0$ are equal to $4$ or $5$, hence $a_{4,0}+a_{5,0}=4$ which leads to a contradiction with corollary 3. Therefore, $n\leqslant 5$.
Note: One can further prove that the only selfish tables are $$\begin{tabular}{ | l | l | l | l | l |} \hline 1 & 0 & 3 & 3 & 4 \\ \hline 1 & 3 & 2 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 0 \\ \hline 2 & 1 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{tabular} \quad \text{and} \quad \begin{tabular}{ | l | l | l | l | l |} \hline 1 & 0 & 4 & 4 & 3 \\ \hline 1 & 4 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 0 & 0 & 0 \\ \hline \end{tabular}$$