IMO олимпиада по математике 2014 года | Казахстанские олимпиады

Пусть $n\ge 2$ — целое число. Дана шахматная доска $n\times n$, состоящая из ${{n}^{2}}$ единичных клеток. Расстановка $n$ ладей в клетках этой доски называется мирной, если в каждом горизонтальном и в каждом вертикальном ряду находится ровно по одной ладье. Найдите наибольшее целое положительное $k$ такое, что для каждой мирной расстановки $n$ ладей найдется клетчатый квадрат $k\times k$, ни в одной из ${{k}^{2}}$ клеток которого нет ладьи.