, 2013

We shall prove that the solution of the problem is $k = nm + 1$.

Suppose that the problem were solvable for a $k \le nm$. Let $A$ be a subset of $S$ that contains all pairs of natural numbers $(x, y)$ such that $1 \le x \le m$ and $1 \le y \le n$. Then $|A| = mn$. Consider $m+1$ arbitrary elements of this set. Since the first coordinate of any of them is between $1$ and $m$, according to Dirichlet's principle there would exist two pairs with the same first coordinate. This would be a contradiction with the conditions of the problem. The same would hold for any subset of $A$ with $k$ elements, hence $k$ cannot be less than or equal to $nm$.

Now consider any set $P \subseteq S$ with $nm + 1$ elements. Divide $S$ into $n$ sets $B_i = \{(x, y) ; x + y \equiv i \pmod{n}, 1 \le x, y \le n\}$ for $i = 1, 2, \dots, n$. The sets are pairwise disjoint, each has exactly $n$ elements, and their union is the entire set $S$. Because $|P| = nm + 1$, according to Dirichlet's principle there must exist a set $B_{i_0}$, which contains at least $m + 1$ elements from $P$. Suppose $(x_1, y_1), (x_2, y_2) \in B_{i_0}$ are two different elements. If $x_1 = x_2$, then from $x_1 + y_1 \equiv i_0 \equiv x_2 + y_2 \pmod{n}$ we derive $y_1 \equiv y_2 \pmod{n}$. Since $1 \le y_1, y_2 \le n$, we have $y_1 = y_2$. This is in contradiction with the assumption that the elements are different. We conclude that the elements of $B_{i_0}$ have pairwise different first coordinates and pairwise different second coordinates. Hence, if we chose $m + 1$ elements from $P$ such that they all are also elements of $B_{i_0}$, they do fulfil the conditions of the problem.