This is the second problem on the IMO2014 problem list:
Let n $\ge 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.
On an $n\times n$ chessboard we want to place $n$ rooks -- this observation makes the problem so easy. Since on an $n\times n$ board there are $\left\lfloor\dfrac{n^2}{k^2}\right\rfloor$ many disjoint $k\times k$ squares, by the pigeonhole principle $k$ must be the largest such that $n\leq\dfrac{n^2}{k^2}$. In fact, $n=\left\lfloor\dfrac{n^2}{k^2}\right\rfloor$ and therefore $k=\lfloor\sqrt{n}\rfloor$.
I found this solution to the problem: http://imomath.com/index.php?options=924, which I think is an overkill. Why would someone post such a lengthy solution when there is a much simpler one? These make me think that my solution is wrong, is it?
Your argument is wrong in several places. There are $(n-k+1)^2$ possible $k\times k$ squares that need to be considered. If you only consider a few of them, say a nonoverlapping subset, you will only consider $\lfloor \frac nk\rfloor^2$ such squares. Then indeed, if $\lfloor \frac nk\rfloor^2>n$, you can be sure that there exists a $k\times k$ that contains no rook. And if $k\le \sqrt n$, then $\frac nk\ge \sqrt n$, but not necessarily $\lfloor\frac nk\rfloor ^2>n$.
It is not even correct that $k=\lfloor\sqrt n\rfloor$ would imply $n=\lfloor\frac {n^2}{k^2}\rfloor$: Consider $n=5$, then $k=2$ and $\lfloor\frac {n^2}{k^2}\rfloor=6$.
Finally, you do not even make use of the peacefulness-condition, hence your estimate may be wrong.