answer(no solution)

The answer is $N=n(k-1)^2$ Construction: color each column by the column number's remainder mod $(k-1)$. Proof of optimality. Lemma (Key observation): A $(k-1)^2+1$- group cannot be selected. Proof. This group must be colored with at most $k-1$ colors, done by pigeonhole. Consider a bipartite graph where each row and each column is a vertex, and two vertices share an edge if and only if the intersection between that row and column is selected. By our lemma, the maximal matching has $(k-1)^2$ edges. Let $r_i$ denote the node representing $i$th row and $c_i$ denote the node representing $i$th column. Consider one maximal matching $a_1-b_1, a_2-b_2, \cdots, a_{(k-1)^2}-b_{(k-1)^2}$. Call an edge external if exactly one of its endpoints is in the matching, and internal otherwise (two vertices in matching). Let $\deg^+(v)$ denote the number of external edges with one vertex and define $\deg^-(v)$ similarly. The number of edges is $\sum\limits_{i=1}^{(k-1)^2} \deg^+(r_i)+\deg^+(c_i)+\deg^-(r_i)$. Note $\sum\limits_{i=1}^{(k-1)^2} \deg^-(a_i)\le \sum\limits_{i=1}^{(k-1)^2}(k-1)^2 = (k-1)^4$. Note $\deg^+(r_i)\deg^+(c_i)=0$ because if $\deg^+(r_i), \deg^+(c_i)>0$, then we can create a bigger matching. Therefore, $\deg^+(r_i)+\deg^+(c_i)\le n-(k-1)^2$. Summing produces the desired result.

Remark: Same thought process as Click to reveal hidden text

. The Chinese official solution finishes it with induction and calls it "trivial". As someone who has solved the problem, I have actually tried that approach and didn't find a solution with it. Can someone provide the details of an inductive solution that shows if we have $mn+1$ squares on an $n\cdot n$ grid, there must exist an $m+1$-group?

KaiDaMagical336 wrote: The answer is $N=n(k-1)^2$ Construction: color each column by the column number's remainder mod $(k-1)$. Proof of optimality. Lemma: A $(k-1)^2+1$- group cannot be selected. Proof. This group must be colored with at most $k-1$ colors, done by pigeonhole. Consider a bipartite graph where each row and each column is a vertex, and two vertices share an edge if and only if the intersection between that row and column is selected. By our lemma, the maximal matching has $(k-1)^2$ edges. Let $r_i$ denote the node representing $i$th row and $c_i$ denote the node representing $i$th column. Consider one maximal matching $a_1-b_1, a_2-b_2, \cdots, a_{(k-1)^2}-b_{(k-1)^2}$. Call an edge external if exactly one of its endpoints is in the matching, and internal otherwise (two vertices in matching). Let $\deg^+(v)$ denote the number of external edges with one vertex and define $\deg^-(v)$ similarly. The number of edges is $\sum\limits_{i=1}^{(k-1)^2} \deg^+(r_i)+\deg^+(c_i)+\deg^-(r_i)$. Note $\sum\limits_{i=1}^{(k-1)^2} \deg^-(a_i)\le \sum\limits_{i=1}^{(k-1)^2}(k-1)^2 = (k-1)^4$. Note $\deg^+(r_i)\deg^+(c_i)=0$ because if $\deg^+(r_i), \deg^+(c_i)>0$, then we can create a bigger matching. Therefore, $\deg^+(r_i)+\deg^+(c_i)\le n-(k-1)^2$. Summing produces the desired result.

Remark: Same thought process as Click to reveal hidden text

. The Chinese official solution finishes it with induction and calls it "trivial". As someone who has solved the problem, I have actually tried that approach and didn't find a solution with it. Can someone provide the details of an inductive solution that shows if we have $mn+1$ squares on an $n\cdot n$ grid, there must exist an $m+1$-group? Consider a maximal group with size $M$ on an $n\times n$ grid. W.l.o.g, let the group be $G=\{(1,1)(2,2)\cdots(M,M)\}$. Define $A_i=\{(i,j)|j>M\}, B_i=\{(j,i)|j>M\}$ for $i=1,2,\ldots,M$; Then $A_i,B_i$ cannot both have square otherwise suppose $(i,Y),(X,i)$ colored, then we a larger group $G+(i,Y)+(X,i)-(i,i)$. Hence on $\cup_{i=1}^n A_i\cup\cup_{i=1}^n B_i$ we can at most have $(n-M)M$ squares. The rest part is trivial with at most $M^2$ squares. Now we get $(n-M)M+M^2\ge mn+1$, thus $M\ge m+1$.

This is just a non-graph theoretical rephrasement of my solution, and doesn't use induction.

CANBANKAN wrote: The answer is $N=n(k-1)^2$ Construction: color each column by the column number's remainder mod $(k-1)$. Proof of optimality. Lemma (Key observation): A $(k-1)^2+1$- group cannot be selected. Proof. This group must be colored with at most $k-1$ colors, done by pigeonhole. Consider a bipartite graph where each row and each column is a vertex, and two vertices share an edge if and only if the intersection between that row and column is selected. By our lemma, the maximal matching has $(k-1)^2$ edges. Let $r_i$ denote the node representing $i$th row and $c_i$ denote the node representing $i$th column. Consider one maximal matching $a_1-b_1, a_2-b_2, \cdots, a_{(k-1)^2}-b_{(k-1)^2}$. Call an edge external if exactly one of its endpoints is in the matching, and internal otherwise (two vertices in matching). Let $\deg^+(v)$ denote the number of external edges with one vertex and define $\deg^-(v)$ similarly. The number of edges is $\sum\limits_{i=1}^{(k-1)^2} \deg^+(r_i)+\deg^+(c_i)+\deg^-(r_i)$. Note $\sum\limits_{i=1}^{(k-1)^2} \deg^-(a_i)\le \sum\limits_{i=1}^{(k-1)^2}(k-1)^2 = (k-1)^4$. Note $\deg^+(r_i)\deg^+(c_i)=0$ because if $\deg^+(r_i), \deg^+(c_i)>0$, then we can create a bigger matching. Therefore, $\deg^+(r_i)+\deg^+(c_i)\le n-(k-1)^2$. Summing produces the desired result.

Remark: Same thought process as Click to reveal hidden text

. The Chinese official solution finishes it with induction and calls it "trivial". As someone who has solved the problem, I have actually tried that approach and didn't find a solution with it. Can someone provide the details of an inductive solution that shows if we have $mn+1$ squares on an $n\cdot n$ grid, there must exist an $m+1$-group? One can just use Kőnig's theorem. Then maximal matching = minimal vertex cover, so any set without $(k-1)^2+1$ group can be covered by $(k-1)^2$ rows-or-columns. Now the thesis is straightforward.

CANBANKAN wrote: [...]Can someone provide the details of an inductive solution that shows if we have $mn+1$ squares on an $n\cdot n$ grid, there must exist an $m+1$-group? We use induction on the number of vertices. The base cases are trivial. Now suppose the claim is true for $n-1$ and we'll prove it for $n.$ Pick any vertice of the $nm+1$ selected; we can assume without loss of generality that the picked vertice lies on the first row and first column. Now delete the first row and first column and look at the $(n-1) \times(n-1)$ remaining board. It has at least $(nm+1)-(2n-1) > (n-1)(m-2) +1 $ selected vertices and hence by our induction hipothesis it has a $(m-1)$ group. Let this group be $v_1,v_2,...v_{m-1}.$ Now suppose that exist a sellected vertice $u$ which is on the fist row and its column is different from $v,v_1,v_2,..., v_{m-1}$, and a sellected vertice $w$ which is on the first column and its row is different from $v,v_1,v_2,..., v_{m-1}.$ If such $u,w$ vertcise exists, then $u,w,v_1,...,v_{m-1}$ forms a $(m+1)$ group and we are done. Now if such vertices does not exists then the number of sellected vertices in either the first row or the first column (including $v$) is at most $n+m-1.$ Hence after deleting the first row and the first column it will remain at least $nm+1 -(n+m-1) > (n-1)(m-1) +1$ sellected vertices, and then by our induction hipothesis there are a $m$ group in the remaing $(n-1)\times (n-1)$ board. Adding $v$ to this group we find a $(m+1)$ group in the initialy sellected points. So done.

I am going to add another proof of the key lemma used in the above solutions, which I found in pad's solution to USAMO 2022/1. Basically the idea is to evaluate the expected value of selected points in a $n-$group choosen at random. We want to show that given $mn +1$ selected squares in a $n\times n$ grid, where $0\le m<n$ are integers, there must exist a $m+1-$group formed only with selected squares. For each permutation $\pi$ of the numbers $1,2,...,n,$ let $s(\pi)$ denote the number of selected squares in the $n$ squares $(1,\pi(i)), (2,\pi(2)),....(n,\pi(n))$ (where $(i,j)$ is the square placed at the $i-$th row and $j$-th column.) Note that the probability of $(i,\pi(i))$ be a selected square is $\frac{mn+1}{n^2}$ and then, by lineality of expectation, the expected value of $s(\pi)$ must be $n \times \frac{mn+1}{n^2} = m + \frac{1}{n}$ and there must be a $n-$group with at lest $m+1$ selected points.

Nice problem! In any proof this lemma is essential: PHSH wrote: We want to show that given $mn +1$ selected squares in a $n\times n$ grid, where $0\le m<n$ are integers, there must exist a $m+1-$group formed only with selected squares. Here is another way to prove: We color the $n\times n$ grid $(i,j)$ by $j-i\mod n.$ Then at least one color have $\lceil\frac{mn+1}n\rceil =m+1$ grids. They form a $m+1$-group.$\Box$ Now by lemma when $N\ge n(k-1)^2+1$ there exists $(k-1)^2+1$-group. In the group if there are $k$ colors, the $k$-group they form gives contradiction. Otherwise if only $\le k-1$ colors, at least one of them is used at least $\lceil\frac{(k-1)^2+1}{k-1}\rceil =k$ times, take them we also get contradiction.$\Box$