Wiersze i kolumny

Przestrzenie wektorowe, bazy, liniowa niezależność, macierze.... Formy kwadratowe, twierdzenia o klasyfikacji...
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 5847
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2393 razy
Pomógł: 643 razy

Wiersze i kolumny

Post autor: mol_ksiazkowy » 14 lip 2019, o 20:43

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
Użytkownik
Użytkownik
Posty: 1110
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 155 razy

Re: Wiersze i kolumny

Post autor: Mruczek » 17 lip 2019, o 16:44

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:
https://artofproblemsolving.com/communi ... 831p366683.

Raczej z kombinatoryki niż algebry liniowej.

ODPOWIEDZ