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.