Wiersze i kolumny

[mol_ksiazkowy]

W macierzy kwadratowej \(\displaystyle{ n \times n}\), której elementami są liczby całkowite nieujemne; jeśli \(\displaystyle{ a_{i, j}=0}\) to suma wszystkich elementów \(\displaystyle{ i}\) tego wiersza i \(\displaystyle{ j}\) tej kolumny jest większa bądź równa \(\displaystyle{ n}\). Udowodnić, że suma wszystkich elementów tej macierzy nie jest mniejsza niż \(\displaystyle{ \frac{n^2}{2}}\).

[Mruczek]

Ja umiem pokazać tylko, że suma jest nie mniejsza niż \(\displaystyle{ \frac{n^2}{4}}\).
Rozpatrzmy dwa przypadki.
Jeżeli w macierzy jest nie więcej niż \(\displaystyle{ \frac{n^2}{2}}\) zer to jest też nie mniej niż \(\displaystyle{ \frac{n^2}{2}}\) liczb całkowitych dodatnich, więc ich suma jest nie mniejsza niż \(\displaystyle{ \frac{n^2}{2}}\).
Pozostaje przypadek w którym w macierzy jest więcej niż \(\displaystyle{ \frac{n^2}{2}}\) zer. Niech \(\displaystyle{ X}\) to zbiór par \(\displaystyle{ (i, j)}\), takich że w wierszu \(\displaystyle{ i}\) i kolumnie \(\displaystyle{ j}\) stoi zero. Wtedy \(\displaystyle{ |X| > \frac{n^2}{2}}\). Niech \(\displaystyle{ k_i}\) to suma kolumny \(\displaystyle{ i}\), a \(\displaystyle{ w_i}\) to suma wiersza \(\displaystyle{ i}\). Sumujemy sumy z wierszy i kolumn po wszystkich pozycjach z zerami:
\(\displaystyle{ \sum_{(i, j) \in X}k_i + w_j \ge \sum_{(i, j) \in X} n = |X| \cdot n > \frac{n^3}{2}}\).
Każda liczba mogła zostać zsumowana nie więcej niż \(\displaystyle{ 2n}\) razy, więc łączna suma jest nie mniejsza niż \(\displaystyle{ \frac{n^2}{4}}\).-- 17 lipca 2019, 19:04 --To zadanie nr 6 z IMO 1971:

Kod: Zaznacz cały

https://artofproblemsolving.com/community/c6h60831p366683

.

Raczej z kombinatoryki niż algebry liniowej.