LVI OM - III - Zadanie 3

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

W kwadratowej tablicy o wymiarach $2n \times 2n$ , gdzie $n$ jest liczbą naturalną, znajduje się $4n^2$ liczb rzeczywistych o sumie równej 0 (na każdym polu tablicy jedna liczba). Wartość bezwzględna każdej z tych liczb jest nie większa od 1. Dowieść, że wartość bezwzględna sumy wszystkich liczb z pewnego rzędu (poziomego lub pionowego) nie przekracza $n$ .

Rozwiązanie

Ponumerujmy wiersze i kolumny danej tablicy liczbami $1,2,\ldots, 2n$ .

Niech $r_1,r_2,\ldots ,r_{2n}$ będą sumami liczb napisanych w wierszach o numerach $1,2,\ldots,2n$ , a $c_1,c_2,\ldots,c_{2n}$ sumami liczb znajdujących się w kolumnach o numerach $1,2,\ldots,2n$ . Zmieniając numerację wierszy oraz kolumn możemy założyć, że $r_1 \geq r_2 \geq \ldots \geq r_{2n}$ oraz $c_i \geq c_2 \geq \ldots \geq c_{2n}$ .

Oznaczmy przez $A$ , $B$ , $C$ , $D$ sumy liczb w czterech ćwiartkach tablicy, jak pokazuje rysunek 3.

Wówczas $A + B + C + D = 0$ , skąd wynika, że w ciągu $(A,B,C,D,A)$ istnieją dwie kolejne liczby, z których jedna jest nieujemna, a druga niedodatnia. Przyjmijmy na przykład, że $AB \leq 0$ . Rozumowanie w pozostałych przypadkach jest analogiczne.

Liczby $A$ i $B$ powstały z sumowania $n^2$ liczb rzeczywistych o wartości bezwzględnej nie większej niż 1, a więc $|A| \leq n^2$ oraz $|B| \leq n^2$ . Jedna z liczb $A$ , $B$ jest nieujemna, a druga niedodatnia, więc $|A + B| \leq max(|A|,|B|) \leq n^2$ . Stąd otrzymujemy również $|C + D| = | A + B| \leq n^2$ .

Jeżeli $r_n \geq 0$ , to liczby $r_1 ,r_2,\ldots,r_n$ są nieujemne. Wtedy ich suma $A + B$ jest też nieujemna, skąd uzyskujemy $r_1 + r_2 +\ldots + r_n = A + B \leq n^2$ . Zatem co najmniej jedna z (nieujemnych) liczb $r_1,r_2,\ldots ,r_n$ nie przekracza $n$ .

Jeżeli natomiast $r_n < 0$ , to liczby $r_{n+1},r_{n+2},\ldots, r_{2n}$ są ujemne i ich suma wynosi $C + D$ . Wtedy $|r_{n+1}| + |r_{n+2}| +\ldots + |r_{2n}| = |C + D|\leq n^2$ . Stąd wynika, że co najmniej jedna z liczb $|r_{n+1}, |r_{n+2}|,\ldots,|r_{2n}|$ nie przekracza $n$ .

To dowodzi zadania.