Min max w tablicy
-
mol_ksiazkowy
- Użytkownik
- Posty: 11373
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Min max w tablicy
Na ile sposobów \(\displaystyle{ n^2}\) różnych liczb rzeczywistych może być elementami w tablicy \(\displaystyle{ n \times n}\) tak, by \(\displaystyle{ \max_{j} \ \min_{i} a_{i, j} = \min_{i} \ \max_{j} a_{i, j}}\) ?
-
arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Min max w tablicy
Dla ułatwienia możemy sobie przyjąć, że liczby rzeczywiste z tej macierzy możemy zamienić na liczby naturalne od jeden do \(\displaystyle{ n^2}\) - wszystkie są różne.
Pamiętajmy, że wszystkich ustawień \(\displaystyle{ n^2}\) liczb w takiej macierzy jest:
\(\displaystyle{ \left[ n^2\right]!}\)
niech naszą równość z zadania spełnia liczba \(\displaystyle{ x}\).
Niech \(\displaystyle{ x}\) ma współrzędne \(\displaystyle{ (i,j)}\),
z obserwacji łatwo zauważyć, że: \(\displaystyle{ x \in\left\langle n;n^2-n+1\right\rangle}\)
Zauważyć łatwo, że wiersz w którym stoi \(\displaystyle{ x}\) zawiera liczby mniejsze od \(\displaystyle{ x}\) z wyjątkiem \(\displaystyle{ x}\).
jest możliwości: \(\displaystyle{ {x-1 \choose n-1}(n-1)!}\)
Kolumna w której jest nasz \(\displaystyle{ x}\) zawiera liczby większe od \(\displaystyle{ x}\) z wyjątkiem \(\displaystyle{ x}\) na sposobów:
\(\displaystyle{ {n^2-x \choose n-1}(n-1)!}\)
Pozostałych układów jest:
\(\displaystyle{ \left[ (n-1)^2\right]!}\)
Teraz wszystkich rozmieszczeń ixa w całej macierzy jest - \(\displaystyle{ n^2}\)
Reasumując te obserwacje powinniśmy otrzymać ilość możliwości:
\(\displaystyle{ \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1} {n^2-x \choose n-1}\left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2=}\)
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\)
Dla \(\displaystyle{ n=2}\) sprawdzałem działa, wynosi jak łatwo sprawdzić \(\displaystyle{ 16}\) co pokrywa się ze sprawdzeniem na piechotę bo tu jeszcze się da ogarnąć...
Pamiętajmy, że wszystkich ustawień \(\displaystyle{ n^2}\) liczb w takiej macierzy jest:
\(\displaystyle{ \left[ n^2\right]!}\)
niech naszą równość z zadania spełnia liczba \(\displaystyle{ x}\).
Niech \(\displaystyle{ x}\) ma współrzędne \(\displaystyle{ (i,j)}\),
z obserwacji łatwo zauważyć, że: \(\displaystyle{ x \in\left\langle n;n^2-n+1\right\rangle}\)
Zauważyć łatwo, że wiersz w którym stoi \(\displaystyle{ x}\) zawiera liczby mniejsze od \(\displaystyle{ x}\) z wyjątkiem \(\displaystyle{ x}\).
jest możliwości: \(\displaystyle{ {x-1 \choose n-1}(n-1)!}\)
Kolumna w której jest nasz \(\displaystyle{ x}\) zawiera liczby większe od \(\displaystyle{ x}\) z wyjątkiem \(\displaystyle{ x}\) na sposobów:
\(\displaystyle{ {n^2-x \choose n-1}(n-1)!}\)
Pozostałych układów jest:
\(\displaystyle{ \left[ (n-1)^2\right]!}\)
Teraz wszystkich rozmieszczeń ixa w całej macierzy jest - \(\displaystyle{ n^2}\)
Reasumując te obserwacje powinniśmy otrzymać ilość możliwości:
\(\displaystyle{ \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1} {n^2-x \choose n-1}\left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2=}\)
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\)
Dla \(\displaystyle{ n=2}\) sprawdzałem działa, wynosi jak łatwo sprawdzić \(\displaystyle{ 16}\) co pokrywa się ze sprawdzeniem na piechotę bo tu jeszcze się da ogarnąć...
-
hannahannah
- Użytkownik
- Posty: 30
- Rejestracja: 30 sty 2015, o 09:23
- Płeć: Kobieta
- Lokalizacja: ba
- Pomógł: 15 razy
Min max w tablicy
Niezupełnie. Wynik jest prawie OK. Zamiast
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\)
powinno być
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot (n!)^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\).
Uzasadnienie:
Tablica = macierz \(\displaystyle{ A=(a_{ij})}\).
Niech
\(\displaystyle{ a=\min_i\max_j a_{ij}=\max_j\min_i a_{ij}}\).
Zamiana miejscami wierzy lub kolumn nie wpływa na istnienie i wartość \(\displaystyle{ a}\), można zatem przyjąć, że \(\displaystyle{ a=a_{11}}\) oraz, że \(\displaystyle{ a_{11}}\) jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli \(\displaystyle{ a_{11}}\) jest najmniejszym elementem w kolumnie i największym w wierszu, to
\(\displaystyle{ \min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}}\).
\(\displaystyle{ \max_j\min_i a_{ij}\le \min_i\max_j a_{ij}}\)
skąd
\(\displaystyle{ \max_j\min a_{ij}=\min_i\max_j a_{ij}=a}\).
Otrzymaliśmy więc lemat: Każdą macierz \(\displaystyle{ A}\) spełniającą warunki zadania można sprowadzić do takiej, że \(\displaystyle{ a_{11}}\) jest największy w kolumnie i najmniejszy w wierszu permutując wiersze i kolumny.
Ponadto to sprowadzenie zachowuje wartość \(\displaystyle{ \max_j\min_i a_{ij}=\min_i\max_j a_{ij}=a}\) (pogrubione, bo odgrywa istotną rolę przy zliczaniu).
Żeby więc otrzymać wynik, zliczamy możliwe ciągi elementów w pierwszej kolumnie i pierwszym wierszu - dokładnie tak jak powyżej:
\(\displaystyle{ \left( (n-1)!\right)^2\sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\)
następnie, znowu tak, jak wyżej, mnożymy przez \(\displaystyle{ ((n-1)^2)!}\), czyli liczbę możliwości wypełnienia reszty macierzy:
\(\displaystyle{ \left( (n-1)!\right)^2 \left( (n-1)^2\right)! \sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\).
W ten sposób otrzymaliśmy liczbę wszystkich macierzy spełniających warunki zadania i takich, że element minimax=maximin to \(\displaystyle{ a_{11}}\).
To należy pomnożyć przez liczbę permutacji wierszy i kolumn, czyli \(\displaystyle{ (n!)^2}\). Skąd ostateczny wynik:
\(\displaystyle{ (n!)^2\left( (n-1)!\right)^2 \left( (n-1)^2\right)! \sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\).
To, że każda macierz zostanie zliczona wynika z lematu, a to, że każda tylko 1 raz z lematu (pogrubiona część) stąd, że pola macierzy są parami różne.
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot n^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\)
powinno być
\(\displaystyle{ \left[ (n-1)!\right]^2 \left[ (n-1)^2\right]! \cdot (n!)^2 \sum_{x=n}^{n^2-n+1} {x-1 \choose n-1}{n^2-x \choose n-1}}\).
Uzasadnienie:
Tablica = macierz \(\displaystyle{ A=(a_{ij})}\).
Niech
\(\displaystyle{ a=\min_i\max_j a_{ij}=\max_j\min_i a_{ij}}\).
Zamiana miejscami wierzy lub kolumn nie wpływa na istnienie i wartość \(\displaystyle{ a}\), można zatem przyjąć, że \(\displaystyle{ a=a_{11}}\) oraz, że \(\displaystyle{ a_{11}}\) jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli \(\displaystyle{ a_{11}}\) jest najmniejszym elementem w kolumnie i największym w wierszu, to
\(\displaystyle{ \min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}}\).
Kod: Zaznacz cały
https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwixg8_xk_XMAhWBtBoKHXyXD48QFggvMAE&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMax%25E2%2580%2593min_inequality&usg=AFQjCNHfMzslr2_XSb2wDCdMjw35Hk5-fg\(\displaystyle{ \max_j\min_i a_{ij}\le \min_i\max_j a_{ij}}\)
skąd
\(\displaystyle{ \max_j\min a_{ij}=\min_i\max_j a_{ij}=a}\).
Otrzymaliśmy więc lemat: Każdą macierz \(\displaystyle{ A}\) spełniającą warunki zadania można sprowadzić do takiej, że \(\displaystyle{ a_{11}}\) jest największy w kolumnie i najmniejszy w wierszu permutując wiersze i kolumny.
Ponadto to sprowadzenie zachowuje wartość \(\displaystyle{ \max_j\min_i a_{ij}=\min_i\max_j a_{ij}=a}\) (pogrubione, bo odgrywa istotną rolę przy zliczaniu).
Żeby więc otrzymać wynik, zliczamy możliwe ciągi elementów w pierwszej kolumnie i pierwszym wierszu - dokładnie tak jak powyżej:
\(\displaystyle{ \left( (n-1)!\right)^2\sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\)
następnie, znowu tak, jak wyżej, mnożymy przez \(\displaystyle{ ((n-1)^2)!}\), czyli liczbę możliwości wypełnienia reszty macierzy:
\(\displaystyle{ \left( (n-1)!\right)^2 \left( (n-1)^2\right)! \sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\).
W ten sposób otrzymaliśmy liczbę wszystkich macierzy spełniających warunki zadania i takich, że element minimax=maximin to \(\displaystyle{ a_{11}}\).
To należy pomnożyć przez liczbę permutacji wierszy i kolumn, czyli \(\displaystyle{ (n!)^2}\). Skąd ostateczny wynik:
\(\displaystyle{ (n!)^2\left( (n-1)!\right)^2 \left( (n-1)^2\right)! \sum_{a=n}^{n^2-n+1} {a-1 \choose n-1}{n^2-a \choose n-1}}\).
To, że każda macierz zostanie zliczona wynika z lematu, a to, że każda tylko 1 raz z lematu (pogrubiona część) stąd, że pola macierzy są parami różne.
-
arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Min max w tablicy
Źle, nie będzie tam \(\displaystyle{ (n!)^2}\)
Bo jak wstawisz za \(\displaystyle{ n=3}\) to z Twojego wzoru wyjdzie \(\displaystyle{ 435456}\) , gdy tymczasem
\(\displaystyle{ 9!=362880}\) , czyli więcej wychodzi ci możliwości niż jest ich wogóle.
a z mojego wzoru wychodzi: \(\displaystyle{ 108864}\)
Twój wzór sprawdzi się tylko dla: \(\displaystyle{ n=1,2}\)
Mnożąc przez \(\displaystyle{ (n!)^2}\) permutując wiersze i kolumny powtarzasz się z permutacjami,
które są wykonane już permutacjach elementów, które nie należą do wiersza i kolumny \(\displaystyle{ (i,j)}\).
Bo jak wstawisz za \(\displaystyle{ n=3}\) to z Twojego wzoru wyjdzie \(\displaystyle{ 435456}\) , gdy tymczasem
\(\displaystyle{ 9!=362880}\) , czyli więcej wychodzi ci możliwości niż jest ich wogóle.
a z mojego wzoru wychodzi: \(\displaystyle{ 108864}\)
Twój wzór sprawdzi się tylko dla: \(\displaystyle{ n=1,2}\)
Mnożąc przez \(\displaystyle{ (n!)^2}\) permutując wiersze i kolumny powtarzasz się z permutacjami,
które są wykonane już permutacjach elementów, które nie należą do wiersza i kolumny \(\displaystyle{ (i,j)}\).
Ostatnio zmieniony 25 maja 2016, o 22:14 przez arek1357, łącznie zmieniany 1 raz.
-
hannahannah
- Użytkownik
- Posty: 30
- Rejestracja: 30 sty 2015, o 09:23
- Płeć: Kobieta
- Lokalizacja: ba
- Pomógł: 15 razy
Min max w tablicy
A faktycznie. Wszystkie możliwe permutacje wierszy i kolumn załatwia czynnik \(\displaystyle{ ((n-1)^2)!\cdot((n-1)!)^2}\).
Poprawię w takim razie to rozumowanie:
Tablica = macierz \(\displaystyle{ A=(a_{ij})}\).
Niech
\(\displaystyle{ a=\min_i\max_j a_{ij}=\max_j\min_i a_{ij}}\).
Wtedy istnieją \(\displaystyle{ s,t}\) takie, że \(\displaystyle{ a=a_{st}}\) i \(\displaystyle{ a_{st}}\) jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli \(\displaystyle{ a=a_{st}}\) jest najmniejszym elementem w kolumnie i największym w wierszu, to
\(\displaystyle{ \min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}}\).
\(\displaystyle{ \max_j\min_i a_{ij}\le \min_i\max_j a_{ij}}\)
skąd
\(\displaystyle{ \max_j\min_i a_{ij}=\min_i\max_j a_{ij}=a}\).
Otrzymaliśmy więc lemat: Macierz \(\displaystyle{ A}\) spełnia warunki zadania wtedy i tylko wtedy, gdy istnieją \(\displaystyle{ s,t}\) takie, że \(\displaystyle{ a_{st}}\) jest największy w kolumnie i najmniejszy w wierszu.
A dalej już tylko zliczanie.
Poprawię w takim razie to rozumowanie:
Tablica = macierz \(\displaystyle{ A=(a_{ij})}\).
Niech
\(\displaystyle{ a=\min_i\max_j a_{ij}=\max_j\min_i a_{ij}}\).
Wtedy istnieją \(\displaystyle{ s,t}\) takie, że \(\displaystyle{ a=a_{st}}\) i \(\displaystyle{ a_{st}}\) jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli \(\displaystyle{ a=a_{st}}\) jest najmniejszym elementem w kolumnie i największym w wierszu, to
\(\displaystyle{ \min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}}\).
Kod: Zaznacz cały
https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwixg8_xk_XMAhWBtBoKHXyXD48QFggvMAE&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMax%25E2%2580%2593min_inequality&usg=AFQjCNHfMzslr2_XSb2wDCdMjw35Hk5-fg\(\displaystyle{ \max_j\min_i a_{ij}\le \min_i\max_j a_{ij}}\)
skąd
\(\displaystyle{ \max_j\min_i a_{ij}=\min_i\max_j a_{ij}=a}\).
Otrzymaliśmy więc lemat: Macierz \(\displaystyle{ A}\) spełnia warunki zadania wtedy i tylko wtedy, gdy istnieją \(\displaystyle{ s,t}\) takie, że \(\displaystyle{ a_{st}}\) jest największy w kolumnie i najmniejszy w wierszu.
A dalej już tylko zliczanie.