Problem

Source: 2021 China TST, Test 1, Day 1 P2

Tags: combinatorics



Given positive integers $n$ and $k$, $n > k^2 >4.$ In a $n \times n$ grid, a $k$-group is a set of $k$ unit squares lying in different rows and different columns. Determine the maximal possible $N$, such that one can choose $N$ unit squares in the grid and color them, with the following condition holds: in any $k$-group from the colored $N$ unit squares, there are two squares with the same color, and there are also two squares with different colors.