6. A natural number $k$ is said to be $n$-squared if, by coloring the cells of a $2 n \times k$ chessboard with $n$ different colors in any way, there exist 4 distinct cells of the same color whose centers are the vertices of a rectangle with sides parallel to the sides of the chessboard.

Determine, as a function of $n$, the smallest natural number $k$ that is $n$-squared.
Solution: We want to prove that $2 n^{2}-n+1$ is the smallest natural number that is $n$-squared. We divide the proof into 2 steps:

- $k \geq 2 n^{2}-n+1$ is $n$-squared. For simplicity, let's say the chessboard has $2 n$ rows and $k$ columns. We call a vertical pair a pair of cells of the same color that are in the same column. In each column, there are at least $n$ vertical pairs: with $n$ colors available, we have at most $n$ cells colored with different colors, and then each of the remaining (which are at least $n$) will form a vertical pair with one of the previously considered cells. Therefore, in the chessboard, there are at least $n \cdot k$ vertical pairs.

Let $C$ be the number of vertical pairs in the chessboard and $c_{i}$ be the number of vertical pairs of the $i$-th color. Then $C=c_{1}+c_{2}+\ldots+c_{n}$. Since $C \geq n \cdot k$, it follows that there exists a color $i_{0}$ such that $c_{i_{0}} \geq k$. There are $\left(\begin{array}{c}2 n \\ 2\end{array}\right)=n(2 n-1)$ possible configurations for a vertical pair within a column. Therefore, for $k \geq 2 n^{2}-n+1$, there are definitely two vertical pairs of color $i_{0}$ in the same configuration, which together form a rectangle that satisfies the requirements of the problem.

Thus, every $k \geq 2 n^{2}-n+1$ is $n$-squared.

- $k \leq 2 n^{2}-n$ is not $n$-squared. It suffices to show that $2 n^{2}-n$ is not $n$-squared. To do this, we show that a $2 n \times (2 n^{2}-n)$ chessboard can be colored with $n$ colors in such a way that there are no rectangles that satisfy the problem's requirements, i.e., there are no two vertical pairs of the same color in the same configuration. It actually suffices to color a "small" $2 n \times (2 n-1)$ chessboard so that there is exactly one vertical pair for each configuration; by cycling the colors, we obtain another $n-1$ chessboards that can be placed next to this one to form the required $2 n \times (2 n^{2}-n)$ chessboard.

To create the "small" chessboard, it is convenient to look at it this way: the rows represent teams, the columns represent match days, and the vertical pairs are the matches. The conditions imposed on the vertical pairs translate into the requirement to organize a tournament for $2 n$ teams, with $2 n-1$ match days, where each team meets every other team exactly once and in each match day, each team plays exactly one match. To organize the tournament, we can proceed as follows: consider a regular $(2 n-1)$-gon and a point outside where the vertices of the polygon are the teams $1, \ldots, 2 n-1$ and the external point is team $2 n$; the matches of day $k$ are all the diagonals parallel to each other that leave out vertex $k$, which will play against $2 n$. 

Now it suffices to assign $n$ different colors to the $n$ matches of the same day and the color of the match to the two teams that play it.

![](https://cdn.mathpix.com/cropped/2024_04_17_d9094f9b7bfdfc478929g-4.jpg?height=731&width=974&top_left_y=1916&top_left_x=147)[^1]

[^0]:    ${ }^{1} T$ can be described as the symmetric of $O$, the midpoint of $M N$, with respect to the circumcenter of triangle $A O A^{\prime}$. The circumcircle of triangle $A O A^{\prime}$ is the Feuerbach (or 'nine-point') circle of triangle $M R N$, so its center is the midpoint of the segment with endpoints $K$ and the circumcenter of $M R N$; from this it follows that the projection of $T$ onto $M N$ coincides with the projection of $K$ onto $M N$, that is,

[^1]:    ${ }^{2}$ By taking the $2 n$-th team apart, on the $k$-th day, team $k$ plays against team $2 n$ while the $i$-th team plays against the $j$-th team where $i+j-2 \cdot k$ is a multiple of $2 n-1$.