Matematyka.pl

Niech \(\displaystyle{ (d_k)_{k=1}^{\infty}}\) będzie ciągiem spełniającym warunek \(\displaystyle{ a_k=a_0+d_k}\) dla każdego całkowitego \(\displaystyle{ k\geq 1}\). Oczywiście \(\displaystyle{ (d_k)}\) jest ciągiem rosnącym. Korzystając z wprowadzonych oznaczeń przekształcamy wyjściową nierówność do postaci Niech \(\displaystyle{ x_k = (k-1)d_{k}-(d_1+d_2+\ldots + d_{k-1})}\). Chcemy pokazać, że istnieje dokładnie jedna liczba całkowita \(\displaystyle{ n\geq 1}\), że \(\displaystyle{ x_n<a_0<x_{n+1}}\). Łatwo zauważyć, że ciąg \(\displaystyle{ (x_k)}\) jest ciągiem rosnącym. Ponieważ \(\displaystyle{ \bigcup (x_k,x_{k+1}]=\mathbb{R}^+}\) oraz przedziały te są parami rozłączne, to istnieje dokładnie jedno \(\displaystyle{ n}\), że \(\displaystyle{ a_0\in (x_n,x_{n+1}]}\) czyli \(\displaystyle{ x_n<a_0\leq x_{n+1}}\), co kończy dowód.

https://www.matematyka.pl/179022,100.htm Porównując rozwiązanie ostatniego zadania wystarczy wziąć jednokładność o środku w \(\displaystyle{ A}\) i skali \(\displaystyle{ 2}\) dla czworokąta \(\displaystyle{ AMNP}\) i koniec

Niech \(\displaystyle{ S}\) będzie punktem wspólnym prostych \(\displaystyle{ BM}\) i \(\displaystyle{ CN}\). Łatwo na kątach otrzymujemy, że \(\displaystyle{ \angle BPA = \angle BAC = \angle CQA}\), skąd \(\displaystyle{ AP = AQ = PM = QN}\) oraz, że \(\displaystyle{ \triangle BPA \sim \triangle BAC \sim \triangle CQA}\). Pokażemy, że \(\displaystyle{ \triangle CQN \sim \triangle MPB \sim \triangle CSB}\) i to da nam tezę, bo wówczas \(\displaystyle{ \angle BSC = \angle BPM = \pi - \angle BPA = \pi - \angle BAC}\) na mocy podobieństwa i początkowej równości kątów. Ale drugie potrzebne podobieństwo można łatwo wyciągnąć z pierwszego potrzebnego (na kątach), a pierwsze podobieństwo działa na mocy cechy bkb, bo \(\displaystyle{ \angle BPM = \angle APQ = \angle AQP = \angle CQN}\) oraz \(\displaystyle{ BP/PM = BP/AP = AB/AC = AQ/QC = NQ/QC}\)

Mam nadzieję, że bez blefa, bo trochę późno

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.