XXXIII OM - I - Zadanie 9

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

W szachownicy utworzonej przez podział kwadratu o boku długości $n$ na kwadraty jednostkowe prostymi równoległymi do boków kwadratu rozpatrujemy wszystkie kwadraty, których boki zawarte są w prostych wyznaczających szachownicę. Niech $1 \leq k \leq n$ i $P(k,n)$ oznacza liczbę tych kwadratów, których długości boków nie przekraczają $k$ . Niech $k(n)$ będzie największą spośród takich liczb $k$ , że $P(k, n) \leq \frac{1}{2} P(n, n)$ . Obliczyć $\lim_{n\to \infty} \frac{k(n)}{n}$ .

Rozwiązanie

Na boku szachownicy jest $n - k + 1$ odcinków długości $k$ o końcach w punktach podziału. Stąd wynika, że wszystkich kwadratów o bokach długości $k$ zawartych w prostych wyznaczających szachownicę jest $(n - k + 1)^2$ . Wobec tego mamy następujące wzory:

$ P(n,n) = \sum_{i=1}^n (n-i+1)^2 = \sum_{i=1}^n i^2 = \frac{1}{6} n(n+1)(2n+1), $

$ \begin{split} P(k, n)& = \sum_{i=1}^n (n-i + 1)^2 = \sum_{i=1}^n i^2 - \sum_{i=1}^{n-k} i^2=\\ &= \frac{1}{6} n(n + 1)(2n + 1) - \frac{1}{6} (n - k)(n - k + 1) \cdot (2n - 2k + 1). \end{split} $

Liczba $k(n)$ spełnia nierówność

$ P(k(n),n) < \frac{1}{2} P(n,n)< P(k(n) + 1,n), $

więc

$ \begin{split} n(n + & 1)(2n + 1) - (n - k(n))(n - k(n) + 1)(2n - 2k(n) + 1) \leq \\ & \leq \frac{1}{2} n(n+ 1)(2n+ 1) <\\ & n(n + 1)(2n + 1) - (n - k(n) - 1)(n - k(n))(2n - 2k(n) - 1). \end{split} $

Mnożąc przez $- \frac{1}{n^3}$ różnicę otrzymanej nierówności i $n(n + 1)(2n+ 1)$ mamy:

$ \begin{split} 2 \left( 1 - \frac{k(n)}{n} \right) \left( 1 - \right. & \left. \frac{k(n)}{n} + \frac{1}{n} \right) \left( 1 - \frac{k(n)}{n} + \frac{1}{2n} \right) \geq \left( 1 + \frac{1}{n} \right)\left(1 + \frac{1}{2n} \right) > \\ & > 2 \left( 1 - \frac{k(n)}{n} - \frac{1}{n} \right) \left( 1 - \frac{k(n)}{n} \right) \left( 1 - \frac{k(n)}{n} - \frac{1}{2n} \right). \end{split} $

Powyższa nierówność przyjmuje postać

$ \begin{split} (*) \qquad 2a_n \left( a_n + \frac{1}{n} \right) \left(a_n + \frac{1}{2n} \right) \geq \left( 1 + \frac{1}{n} \right) \left(1 + \frac{1}{2n} \right) > \\ & 2a_n \left( a_n - \frac{1}{n} \right) \left(a_n - \frac{1}{2n} \right), \end{split} $

gdzie $a_n = 1 - \frac{k(n)}{n}$ .

Udowodnimy, że ciąg $\left( 2a_n \left( a_n + \frac{1}{n} \right) \left( a_n + \frac{1}{2n} \right) \right)$ jest zbieżny do liczby $1$ . Gdyby bowiem tak nie było, to wobec nierówności (*) i wobec tego, że $\displaystyle \lim_{n \to \infty} \left( 1 + \frac{1}{n} \right) \left( 1 + \frac{1}{2n} \right) = 1$ mielibyśmy

$ (**) \qquad \exists_{\varepsilon > 0} \forall_{n_0 \in N} \exists_{n>n_0} 2a_n(a_n + \frac{1}{n})(a_n + \frac{1}{2n})>1+\varepsilon. $

Przyjmijmy $n_0$ tak duże, aby były dla każdego $n \geq n_0$ spełnione warunki

$ (***) \qquad \left( 1 + \frac{1}{n} \right) \left( 1 + \frac{1}{2n} \right) < 1+ \frac{\varepsilon}{2} \ \textrm{i} \ \frac{6}{n} < \frac{\varepsilon}{2}. $

Ponieważ

$ \begin{split} \left( a_n + \frac{1}{n} \right)\left( a_n + \right. & \left. \frac{1}{2n} \right)= \left( a_n - \frac{1}{n}+ \frac{2}{n} \right) \left( a_n - \frac{1}{2n}+ \frac{1}{n} \right) =\\ & = \left( a_n - \frac{1}{n} \right)\left( a_n - \frac{1}{2n} \right)+ \frac{a_n}{n} - \frac{1}{n^2} + \frac{2a_n}{n} - \frac{1}{n^2} + \frac{2}{n^2}=\\ & = \left( a_n - \frac{1}{n} \right)\left( a_n - \frac{1}{2n} \right)+ \frac{3a_n}{n} \ \textrm{i} \ 0<a_n<1, \end{split} $

to mamy nierówność

$ \begin{split} 2a_n \left(a_n+\frac{1}{n}\right) \left(a_n + \frac{1}{2n}\right) < 2a_n \left(a_n - \frac{1}{n}\right) \left(a_n - \frac{1}{2n} \right) \left(a_n - \frac{1}{2n}\right) +\frac{6}{n} <\\ < \left(1 + \frac{1}{n} \right) \left(1 + \frac{1}{2n}\right) +\frac{6}{n}, \end{split} $

Na podstawie ostatniej nierówności oraz (***) otrzymujemy

$ 2a_n \left(a_n+\frac{1}{n}\right) \left(a_n + \frac{1}{2n}\right) < 1 + \frac{\varepsilon}{2} + \frac{\varepsilon}{2}= 1 + \varepsilon. $

Sprzeczne to jest z warunkiem (**). Do sprzeczności doprowadziło przypuszczenie, że liczba $1$ nie jest granicą ciągu $2a_n \left( a_n+\frac{1}{n}\right) \left(a_n + \frac{1}{2n} \right)$ . Wobec tego granica tego ciągu istnieje i równa jest $1$ . Analogicznie stwierdzamy, że również ciąg $\left( 2a_n \left( a_n-\frac{1}{n}\right) \left(a_n - \frac{1}{2n}\right) \right)$ jest zbieżny do $1$ . Wobec oczywistej nierówności