Wiersze i kolumny
- mol_ksiazkowy
- Użytkownik
- Posty: 11376
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Wiersze i kolumny
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}}\).
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Wiersze i kolumny
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:
.
Raczej z kombinatoryki niż algebry liniowej.
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.