szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 maja 2016, o 14:02 
Użytkownik

Posty: 5668
Lokalizacja: Kraków
Na ile sposobów n^2 różnych liczb rzeczywistych może być elementami w tablicy n \times n tak, by \max_{j} \ \min_{i} a_{i, j} = \min_{i}  \ \max_{j} a_{i, j} ?
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2016, o 16:41 
Użytkownik
Avatar użytkownika

Posty: 3498
Lokalizacja: blisko
Dla ułatwienia możemy sobie przyjąć, że liczby rzeczywiste z tej macierzy możemy zamienić na liczby naturalne od jeden do n^2 - wszystkie są różne.

Pamiętajmy, że wszystkich ustawień n^2 liczb w takiej macierzy jest:

\left[  n^2\right]!

niech naszą równość z zadania spełnia liczba x.

Niech x ma współrzędne (i,j),

z obserwacji łatwo zauważyć, że: x \in\left\langle  n;n^2-n+1\right\rangle

Zauważyć łatwo, że wiersz w którym stoi x zawiera liczby mniejsze od x z wyjątkiem x.

jest możliwości: {x-1 \choose n-1}(n-1)!

Kolumna w której jest nasz x zawiera liczby większe od x z wyjątkiem x na sposobów:

{n^2-x \choose n-1}(n-1)!

Pozostałych układów jest:

\left[ (n-1)^2\right]!

Teraz wszystkich rozmieszczeń ixa w całej macierzy jest - n^2

Reasumując te obserwacje powinniśmy otrzymać ilość możliwości:

\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=

\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 n=2 sprawdzałem działa, wynosi jak łatwo sprawdzić 16 co pokrywa się ze sprawdzeniem na piechotę bo tu jeszcze się da ogarnąć...
Góra
Kobieta Offline
PostNapisane: 25 maja 2016, o 18:29 
Użytkownik

Posty: 30
Lokalizacja: ba
Niezupełnie. Wynik jest prawie OK. Zamiast

\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ć

\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 A=(a_{ij}).

Niech

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ść a, można zatem przyjąć, że a=a_{11} oraz, że a_{11} jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli a_{11} jest najmniejszym elementem w kolumnie i największym w wierszu, to

\min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}.

Z drugiej strony wiadomo, że dla dowolnej macierzy o wyrazach rzeczywistych:

\max_j\min_i a_{ij}\le \min_i\max_j a_{ij}

skąd

\max_j\min a_{ij}=\min_i\max_j a_{ij}=a.

Otrzymaliśmy więc lemat: Każdą macierz A spełniającą warunki zadania można sprowadzić do takiej, że a_{11} jest największy w kolumnie i najmniejszy w wierszu permutując wiersze i kolumny.
Ponadto to sprowadzenie zachowuje wartość \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:

\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 ((n-1)^2)!, czyli liczbę możliwości wypełnienia reszty macierzy:

\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 a_{11}.

To należy pomnożyć przez liczbę permutacji wierszy i kolumn, czyli (n!)^2. Skąd ostateczny wynik:

(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.
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2016, o 20:46 
Użytkownik
Avatar użytkownika

Posty: 3498
Lokalizacja: blisko
Źle, nie będzie tam (n!)^2

Bo jak wstawisz za n=3 to z Twojego wzoru wyjdzie 435456 , gdy tymczasem

9!=362880 , czyli więcej wychodzi ci możliwości niż jest ich wogóle.

a z mojego wzoru wychodzi: 108864


Twój wzór sprawdzi się tylko dla: n=1,2

Mnożąc przez (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 (i,j).
Góra
Kobieta Offline
PostNapisane: 25 maja 2016, o 21:07 
Użytkownik

Posty: 30
Lokalizacja: ba
A faktycznie. Wszystkie możliwe permutacje wierszy i kolumn załatwia czynnik ((n-1)^2)!\cdot((n-1)!)^2.

Poprawię w takim razie to rozumowanie:

Tablica = macierz A=(a_{ij}).

Niech

a=\min_i\max_j a_{ij}=\max_j\min_i a_{ij}.

Wtedy istnieją s,t takie, że a=a_{st} i a_{st} jest najmniejszym elementem w swojej kolumnie i największym w swoim wierszu. I na odwrót; jeśli a=a_{st} jest najmniejszym elementem w kolumnie i największym w wierszu, to

\min_i\max_j a_{ij}\le a\le \max_j\min_i a_{ij}.

Z drugiej strony wiadomo, że dla dowolnej macierzy o wyrazach rzeczywistych:

\max_j\min_i a_{ij}\le \min_i\max_j a_{ij}

skąd

\max_j\min_i a_{ij}=\min_i\max_j a_{ij}=a.

Otrzymaliśmy więc lemat: Macierz A spełnia warunki zadania wtedy i tylko wtedy, gdy istnieją s,t takie, że a_{st} jest największy w kolumnie i najmniejszy w wierszu.

A dalej już tylko zliczanie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Malejące ciągi liczb w tablicy, Catalan  patry93  1
 Kolorowanie pól w tablicy  andrzej9991  5
 [Algorytmy] Wypełnianie tablicy, sumowanie wartości, minimum  Hajtowy  0
 [Maxima] wypisać w tablicy liczby podzielne przez 6  lolo666  4
 sortowanie tablicy prostokątnej w c  dary  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl