LIX OM - III -Zadanie 1

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

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

$ \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} $

Rozwiązanie

Udowodnimy najpierw, że

$ (1) \qquad a_1 +a_2 + \dots +a_n = \frac{1}{2} n(n^2 +1). $

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

$ (2) \qquad a_i =(i - 1)n +b_i \text{ dla }i =1, 2, \dots, n. $

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

$ b_1 +b_2 +\dots +b_n =1+2+\dots +n = \frac{1}{2}n(n+1) $

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

$ \begin{split} a_1 +a_2 +\dots + a_n &= (0+1+\dots +(n - 1))n +b_1 +b_2 +\dots +b_n = \\ &= \frac{1}{2}(n - 1)n^2 + \frac{1}{2}n(n +1) = \frac{1}{2}n(n^2 +1). \end{split} $

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

$ \begin{split} \frac{1^2}{a_1}+\frac{2^2}{a_2}+\frac{3^2}{a_3}+\dots +\frac{n^2}{a_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} \geqslant \\ &\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}} = \\ &= \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)} = \\ &= \frac{n(n+1)^2}{2(n^2+1)} = \frac{(n+2)(n^2+1)-2}{2(n^2+1)} \\ &= \frac{n+2}{2} - \frac{1}{n^2+1} \end{split} $

czyli tezę zadania.