One side of a square sheet of paper is colored red, the other - in blue. On both sides, the sheet is divided into $n^2$ identical square cells. In each of these $2n^2$ cells is written a number from $1$ to $k$. Find the smallest $k$,for which the following properties hold simultaneously: (i) on the red side, any two numbers in different rows are distinct; (ii) on the blue side, any two numbers in different columns are different; (iii) for each of the $n^2$ squares of the partition, the number on the blue side is not equal to the number on the red side.
Problem
Source: St. Petersburg 2023 9.4=10.4
Tags: combinatorics
bin_sherlo
27.09.2024 18:44
Answer is $\lfloor \frac{4n+2}{3}\rfloor$ for $n$. Construction: For $n=3k,$ we construct two tables with $4k$ numbers. Write $1,2,...,2k$ to first $2k$ rows. Then write $2k+i$ to $(2k+i).$ row except $(2k+i).$ column. After that, write $3k+i$ into the gap on $(2k+i).$ row. For the column table, fill the $(2k+i).$ column with $2k+i$. Fill $(k+j).$ column with $(3k+j)$ for $1\leq j\leq k-1$. For first $k$ columns, we have $2k$ numbers and we can complete each column with different $2$ numbers. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&1&1&1&1&1 \\\hline 2&2&2&2&2&2&2&2&2 \\\hline 3&3&3&3&3&3&3&3&3 \\\hline 4&4&4&4&4&4&4&4&4 \\\hline 5&5&5&5&5&5&5&5&5 \\\hline 6&6&6&6&6&6&6&6&6 \\\hline 7&7&7&7&7&7&10&7&7 \\\hline 8&8&8&8&8&8&8&11&8 \\\hline 9&9&9&9&9&9&9&9&12 \\\hline \end{array} $$$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 5&3&2&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline 5&4&1&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline 6&3&1&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline 5&3&1&10&11&12&7&8&9 \\\hline \end{array} $$For $n=3k+1,$ we will construct two tables with $4k+2$ numbers. Write $1,...,2k$ to first $2k$ rows. Then, write $2k+i$ to $(2k+i).$ row except $(2k+i).$ column. Fill the gaps with $3k+1+i$ in $(2k+i).$ rows. For the column table, write $2k+i$ into $(2k+i).$ column. Fill the $(k-1+i).$ column with $3k+1+i$ for $1\leq i\leq k+1$. We have $k-1 $ columns and $2k$ numbers and we can complete each column with exactly two numbers. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&1&1&1&1&1&1 \\\hline 2&2&2&2&2&2&2&2&2&2 \\\hline 3&3&3&3&3&3&3&3&3&3 \\\hline 4&4&4&4&4&4&4&4&4&4 \\\hline 5&5&5&5&5&5&5&5&5&5 \\\hline 6&6&6&6&6&6&6&6&6&6 \\\hline 7&7&7&7&7&7&11&7&7&7 \\\hline 8&8&8&8&8&8&8&12&8&8 \\\hline 9&9&9&9&9&9&9&9&13&9 \\\hline 10&10&10&10&10&10&10&10&10&14\\\hline \end{array} $$$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 3&2&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 4&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline 3&1&11&12&13&14&7&8&9&10 \\\hline \end{array} $$For $n=3k+2,$ we will construct two tables with $4k+3$ numbers. Write $1,...,2k+1$ to first $2k+1$ rows. Write $2k+i+1$ to $(2k+i+1).$ row except $(2k+i+1).$ column. Fill the gaps in $(2k+i+1).$ row with $3k+i+2$. For the column table, write $2k+1+i$ to $(2k+1+i).$ column. Fill the $(k+i).$ column with $3k+2+i$ for $1\leq i\leq k+1$. We have $2k+1$ numbers to complete first $k$ columns. We can fill each column with exactly two numbers. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&1&1&1&1&1&1&1 \\\hline 2&2&2&2&2&2&2&2&2&2&2 \\\hline 3&3&3&3&3&3&3&3&3&3&3 \\\hline 4&4&4&4&4&4&4&4&4&4&4 \\\hline 5&5&5&5&5&5&5&5&5&5&5 \\\hline 6&6&6&6&6&6&6&6&6&6&6 \\\hline 7&7&7&7&7&7&7&7&7&7&7 \\\hline 8&8&8&8&8&8&8&12&8&8&8 \\\hline 9&9&9&9&9&9&9&9&13&9&9 \\\hline 10&10&10&10&10&10&10&10&10&14&10\\\hline 11&11&11&11&11&11&11&11&11&11&15\\\hline \end{array} $$$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 5&3&2&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 5&4&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 6&3&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline 5&3&1&12&13&14&15&8&9&10&11 \\\hline \end{array} $$Lower Bound: Suppose that there exists a pair of table holds the conditions and it has less than $\lfloor \frac{4n+2}{3}\rfloor$ numbers on it. If a row consists exactly one number, then call that row unique. Similarily define unique for columns. Let there be $m$ unique rows and $k$ unique columns. Since any pair of numbers on a unique row and on a unique column are different, the inequality \[\lfloor\frac{4n-1}{3}\rfloor \geq m+k\]holds. Note that $m+2(n-m)\leq \lfloor\frac{4n-1}{3}\rfloor\iff m\geq 2n-\lfloor\frac{4n-1}{3}\rfloor$ After applying same thing on $k$, we get that \[\lfloor\frac{4n-1}{3}\rfloor \geq m+k\geq 4n-2\lfloor\frac{4n-1}{3}\rfloor\implies 3\lfloor\frac{4n-1}{3}\rfloor\geq 4n\]But $n=3l$ yields $3(3l-1)\geq 12l$ which is not true, $n=3l+1$ gives $3(3l+1)\geq 4(3l+1)$ which is not correct again, $n=3l+2$ implies $3(4l+2)\geq 4(3l+2)$ which is false. Thus, answer is at least $\lfloor\frac{4n+2}{3}\rfloor$ as desired.$\blacksquare$