XXXIII OM - I - Zadanie 9

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:

\[<br />
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),<br />
\]
\[<br />
\begin{split}<br />
P(k, n)& = \sum_{i=1}^n (n-i + 1)^2 = \sum_{i=1}^n i^2 - \sum_{i=1}^{n-k} i^2=\\<br />
&= \frac{1}{6} n(n + 1)(2n + 1) - \frac{1}{6} (n - k)(n - k + 1) \cdot (2n - 2k + 1).<br />
\end{split}<br />
\]

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

\[<br />
P(k(n),n) < \frac{1}{2} P(n,n)< P(k(n) + 1,n),<br />
\]

więc

\[<br />
\begin{split}<br />
n(n + & 1)(2n + 1) - (n - k(n))(n - k(n) + 1)(2n - 2k(n) + 1) \leq \\<br />
& \leq \frac{1}{2} n(n+ 1)(2n+ 1) <\\<br />
& n(n + 1)(2n + 1) - (n - k(n) - 1)(n - k(n))(2n - 2k(n) - 1).<br />
\end{split}<br />
\]

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

\[<br />
\begin{split}<br />
2 \left( 1 - \frac{k(n)}{n} \right)<br />
\left( 1 - \right. & \left. \frac{k(n)}{n} + \frac{1}{n} \right)<br />
\left( 1 - \frac{k(n)}{n} + \frac{1}{2n} \right) \geq<br />
\left( 1 + \frac{1}{n} \right)\left(1 + \frac{1}{2n} \right) > \\<br />
& >  2 \left( 1 - \frac{k(n)}{n} - \frac{1}{n} \right)<br />
 \left( 1 - \frac{k(n)}{n} \right)<br />
 \left( 1 - \frac{k(n)}{n} - \frac{1}{2n} \right).<br />
\end{split}<br />
\]

Powyższa nierówność przyjmuje postać

\[<br />
\begin{split}<br />
(*) \qquad<br />
2a_n \left( a_n + \frac{1}{n} \right) \left(a_n + \frac{1}{2n} \right) \geq<br />
 \left( 1 + \frac{1}{n} \right) \left(1 + \frac{1}{2n} \right) > \\<br />
& 2a_n \left( a_n - \frac{1}{n} \right) \left(a_n - \frac{1}{2n} \right),<br />
\end{split}<br />
\]

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

\[<br />
(**) \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.<br />
\]

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

\[<br />
(***) \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}.<br />
\]

Ponieważ

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

to mamy nierówność

\[<br />
\begin{split}<br />
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} <\\<br />
< \left(1 + \frac{1}{n} \right) \left(1 + \frac{1}{2n}\right) +\frac{6}{n},<br />
\end{split}<br />
\]

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

\[<br />
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.<br />
\]

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

\[<br />
2a_n \left(a_n-\frac{1}{n}\right) \left(a_n - \frac{2}{n}\right) <<br />
2a_n^3 <<br />
2a_n \left(a_n+\frac{1}{n}\right) \left(a_n + \frac{1}{2n}\right)<br />
\]

otrzymujemy na podstawie twierdzenia o trzech ciągach, że

\[<br />
\lim_{n \to \infty} 2a_n^3 = 1,<br />
\lim_{n \to \infty} a_n^3 = \frac{1}{2}.<br />
\]

Ponieważ $ \frac{k(n)}{n} = 1- a_n $ i $ \displaystyle \lim_{n \to \infty} a_n = \frac{1}{\sqrt[3]{2}} $ więc

\[<br />
\lim_{n \to \infty} \frac{k(n)}{n} = 1- \lim_{n \to \infty} a_n =1- \frac{1}{\sqrt[3]{2}}.<br />
\]

Komentarze

Dodaj nową odpowiedź