Question 12
Natural numbers $m$ and $n$ satisfy $n \gt m \ge 1$. Let $S$ be the set of all pairs of natural numbers $(x, y)$ where $1 \le x, y \le n$. Determine the least natural number $k$ such that for each subset $P \subseteq S$ with cardinality $k$ there exist $m+1$ pairs $(x_1, y_1), (x_2, y_2), \dots, (x_{m+1}, y_{m+1}) \in P$ where the numbers $x_1, x_2, \dots, x_{m+1}$ are pairwise distinct and the numbers $y_1, y_2, \dots, y_{m+1}$ are pairwise distinct.