Pokażę, że
\(\displaystyle{ k = \left[ \sqrt{n-1} \right]}\). Najpierw udowodnię, że zawsze da się znaleźć kwadrat
\(\displaystyle{ k \times k}\) bez wieży, a potem, że to maksymalne k. Załóżmy, że przy jakiejś spokojnej konfiguracji nie da się nigdzie umieścić tego kwadratu. Weźmy teraz pole na którym stoi wieża będąca w 1 kolumnie. Wyróżnijmy teraz jakiś prostokąt o wymiarach
\(\displaystyle{ k \times n}\), który zawiera to pole (na pewno jest taki prostokąt). W tym prostokącie jest dokładnie k wież (od teraz bierzemy pod uwagę tylko wieże znajdujące się w tym prostokącie). Uszeregujmy je od lewej do prawej, czyli wieża najbardziej na lewo będzie pierwsza, druga od lewej druga itd. Niech teraz ciąg
\(\displaystyle{ \left( a_{k} \right)}\) będzie określony w ten sposób, że dla i = 1,2,...,k
\(\displaystyle{ a_{i}}\) oznacza numer kolumny, w której znajduję się i-ta wieża. Wtedy w szczególności
\(\displaystyle{ a_{1}=1}\). Założyliśmy, że nie da się umieścić kwadratu bez wieży, więc między i-tą a (i+1)-szą wieżą musi być odstęp mniejszy niż k. Więc musi zachodzić zależność
\(\displaystyle{ a_{i+1} \le a_{i}+k}\) co w połączeniu z
\(\displaystyle{ a_{1}=1}\) daje
\(\displaystyle{ a_{k} \le k^{2}-k+1}\). Teraz korzystając z łatwej do pokazania nierówności(*)
\(\displaystyle{ n \ge k^{2}+1}\) mamy
\(\displaystyle{ n+1 >a_{k}+k}\) i otrzymujemy, że za k-tą wieżą w tym prostokącie zmieści się na pewno jakiś kwadrat
\(\displaystyle{ k \times k}\) który nie będzie miał wieży. Sprzeczność z założeniem, że nigdzie się nie da umieścić kwadratu czyli w ostateczności mamy pierwszą część zadania. Teraz trzeba pokazać, że jest to maksymalne k. W tym celu pokażę spokojną konfigurację, w której nigdzie nie da się umieścić kwadratu
\(\displaystyle{ k+1 \times k+1}\) nie zawierającego wieży. Pokażę kolorowanie, w którym zamalowane pole odpowiada postawionej wieży.
Ponumerujmy wiersze i kolumny zaczynając od lewego górnego rogu od 1 do n. Zamalujmy pole (k+1,k+1) oraz jeśli zostało pomalowane pole (i,j) to malujemy także (i+1,j-k-1) (i-1,j+k+1) (i+k+1,j-1) (i-k-1,j+1) (i-k-1,j-k-1) (i+k+1,j+k+1) (jeśli któreś z tych pól wypada poza planszą to nie malujemy). Żeby jakoś zobrazować to kolorowanie wstawiam przykład dla n = 17 i n = 16 gdzie wtedy k+1 = 5 i k+1 = 4.
Łatwo zauważyć, że wtedy nie da się zmieścić tutaj kwadratu
\(\displaystyle{ k+1 \times k+1}\) (nie będę dowodził, dowód przez ogląd ). No ale jeszcze trzeba pokazać, że liczba tych zamalowanych pól jest mniejsza równa n i że w każdej kolumnie i w każdym wierszu jest 1 wieża. Widać, że między polem (i,j) a (i-1,j+k+1) jest k kolumn, natomiast zamalowanych pól jest
\(\displaystyle{ \left[ \frac{n}{k+1} \right]-1}\). Zatem, żeby pokazać, że w każdej kolumnie jest jedna wieża trzeba aby(**)
\(\displaystyle{ k \ge \left[ \frac{n}{k+1} \right] -1}\). Ta równość jest trywialna, ale potem ją pokażę. Oraz wtedy liczba zamalowanych pól jest równa
\(\displaystyle{ \left[ \frac{n}{k+1} \right] ^{2}}\) ale okazuję się (***), że
\(\displaystyle{ \left[ \frac{n}{k+1} \right] ^{2} \le n}\). Czyli liczba wież jest mniejsza lub równa n, czyli ogólnie to kolorowanie odpowiada spokojnej konfiguracji (jeśli liczba zamalowanych pól jest mniejsza od n to dokładamy wieże w randomowe miejsca tylko żeby zachować własność, że w każdym wierszu i kolumnie ma być jedna wieża). Mamy więc, że k jest maksymalne. Na koniec zadania pokażę łatwe, ale niezbędne dowody własności (*) (**) i (***). Mamy
\(\displaystyle{ k = \left[ \sqrt{n-1} \right] \le \sqrt{n-1}}\) czyli
\(\displaystyle{ k^{2} \le n-1}\) a stąd mamy już zależność (*). Teraz oczywiste jest, że skoro
\(\displaystyle{ \left[ \sqrt{n-1} \right] = k}\) to
\(\displaystyle{ \sqrt{n-1} < k+1}\) czyli
\(\displaystyle{ n-1 < (k+1)^{2}}\) więc
\(\displaystyle{ n \le (k+1)^{2}}\) czyli
\(\displaystyle{ \left[ \frac{n}{k+1} \right] \le \frac{n}{k+1} \le k+1}\) stąd mamy (**). Ale z tego, że
\(\displaystyle{ n \le k+1^{2}}\) mamy
\(\displaystyle{ \frac{n}{ k+1^{2} } \le 1}\) i mnożąc przez n
\(\displaystyle{ \frac{ n^{2} }{ k+1^{2} } \le n}\) stąd już widać że wynika (***). Udowodniłem wszystkie własności więc koniec.
