MathNet 2013 Question 29

Let $k$ and $n$ be two integers satisfying $1 \le k \lt n$. Consider $kn + 1$ rooks placed on an $n \times n$-chessboard. Prove that among them one may find $k + 1$ rooks no two of which attack each other.