LIX OM - III -Zadanie 1

W pola tablicy rozmiaru $ n \times n $ wpisane są liczby $ 1, 2, \dots , n^2 $ , przy czym liczby $ 1, 2, \dots , n $ znajdują
się w pierwszym wierszu (od strony lewej do prawej), liczby $ n +1, n +2, \dots ,2n $ w drugim, itd.

Wybrano $ n $ pól tablicy, z których żadne dwa nie leżą w jednym wierszu ani w jednej kolumnie. Niech $ a_i $ będzie liczbą
znajdującą się w tym wybranym polu, które leży w wierszu o numerze $ i $. Dowieść, że

\[<br />
\frac{1^2}{a_1} + \frac{2^2}{a_2} + \dots + \frac{n^2}{a_n} \geqslant \frac{n+2}{2} - \frac{1}{n^2+1}<br />
\]

Rozwiązanie

Udowodnimy najpierw, że

\[<br />
(1) \qquad a_1 +a_2 + \dots +a_n = \frac{1}{2} n(n^2 +1).<br />
\]

Niech $ b_i $ oznacza numer kolumny, w której znajduje się liczba $ a_i $. Wówczas

\[<br />
(2) \qquad a_i =(i - 1)n +b_i \text{ dla }i =1, 2, \dots, n.<br />
\]

Z warunków zadania wynika, że ciąg $ (b_1,b_2,\dots ,b_n) $ jest permutacją ciągu $ (1, 2,\dots ,n) $. Wobec tego

\[<br />
b_1 +b_2 +\dots +b_n =1+2+\dots +n = \frac{1}{2}n(n+1)<br />
\]

i z uwagi na wzór (2) dowód zależności (1) sprowadza się do rachunku

\[<br />
\begin{split}<br />
a_1 +a_2 +\dots + a_n &= (0+1+\dots +(n - 1))n +b_1 +b_2 +\dots +b_n = \\<br />
&= \frac{1}{2}(n - 1)n^2 + \frac{1}{2}n(n +1) = \frac{1}{2}n(n^2 +1).<br />
\end{split}<br />
\]

Korzystając teraz z równości (1) oraz z nierówności pomiędzy średnią arytmetyczną i harmoniczną otrzymujemy

\[<br />
\begin{split}<br />
\frac{1^2}{a_1}+\frac{2^2}{a_2}+\frac{3^2}{a_3}+\dots +\frac{n^2}{a_n} &=<br />
\frac{1}{a_1} + \frac{2}{a_2} + \frac{2}{a_2} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{4}{a_4} +<br />
\dots \frac{n}{a_n} \geqslant \\<br />
&\geqslant \frac{(1+2+3+\dots +n)}{\frac{1}{a_1} + \frac{2}{a_2} + \frac{2}{a_2} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{4}{a_4} + \dots \frac{n}{a_n}} = \\<br />
&= \frac{\left(\frac{n(n+1)}{2}\right)^2}{a_1+a_2+a_3+\dots+a_n} = \frac{\frac{1}{4}n^2(n+1)^2}{\frac{1}{2}n(n^2+1)} = \\<br />
&= \frac{n(n+1)^2}{2(n^2+1)} = \frac{(n+2)(n^2+1)-2}{2(n^2+1)} \\<br />
&= \frac{n+2}{2} - \frac{1}{n^2+1}<br />
\end{split}<br />
\]

czyli tezę zadania.

Komentarze

Dodaj nową odpowiedź