Zbiór pól na szachownicy.
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
mamy szachownicę \(\displaystyle{ n \cdot n}\). rozważmy zbiory pól szachownicy o następującej własności fi: do zbioru należy minimum k pól z każdego wiersza i każdej kolumny. (możemy abstrakcyjnie myśleć o kwadratowej macierzy stopnia n wypełnionej zerami lub jedynkami i spełniającej własność, że suma z każdego wiersza i z każdej kolumny jest niemniejsza niż k).
Oczywiście \(\displaystyle{ n>0, k \le n}\).
Jak łatwo zauważyć moc takiego zbioru jest \(\displaystyle{ \ge n \cdot k}\).
Pytanie brzmi: czy każdy zbiór mocy \(\displaystyle{ (n \cdot k+t)}\) jest nadzbiorem jakiegoś zbioru o mocy \(\displaystyle{ (n \cdot k+t-1)}\)? Niech \(\displaystyle{ t>0}\).
Uwaga: w warunkach normalnych odpowiedź jest oczywista (tak!, każdy zbiór jest nadzbiorem pewnego zbioru o mocy mniejszej o 1), lecz w naszej rodzinie zbiorów nie zawsze to zachodzi.
Po co to w ogóle rozważać? Otóż wyobraźmy sobie, że wszystkie zbiory określonej mocy mają jakąś cechę (np. spośród zbioru pól na szachownicy można wybrać n takich pól, że, postawiwszy na nich wieże, nie atakują się one parami). Jeśli odpowiedź na nurtujące pytanie jest twierdząca możemy powiedzieć natychmiastowo, że wszystkie zbiory mocy o 1 większej też mają tę cechę.
Można mówić o genetyce zbiorów, o dziedziczeniu pewnych cech z rodziny zbiorów pewnej mocy na rodzinę zbiorów o mocy większej o 1.
Do tej pory ustaliłem, że zachodzi:
dla \(\displaystyle{ t<n-k}\) : nie
dla \(\displaystyle{ t>\frac{(n-k)^{2}}{4}}\) : tak
Jednak wynik nie zachwyca bo "luka" przypadków nierozstrzygniętych rośnie kwadratowo wraz z \(\displaystyle{ (n-k)}\) więc tylko w nietypowych sytuacjach mamy zadowalające rezultaty.
Oczywiście \(\displaystyle{ n>0, k \le n}\).
Jak łatwo zauważyć moc takiego zbioru jest \(\displaystyle{ \ge n \cdot k}\).
Pytanie brzmi: czy każdy zbiór mocy \(\displaystyle{ (n \cdot k+t)}\) jest nadzbiorem jakiegoś zbioru o mocy \(\displaystyle{ (n \cdot k+t-1)}\)? Niech \(\displaystyle{ t>0}\).
Uwaga: w warunkach normalnych odpowiedź jest oczywista (tak!, każdy zbiór jest nadzbiorem pewnego zbioru o mocy mniejszej o 1), lecz w naszej rodzinie zbiorów nie zawsze to zachodzi.
Po co to w ogóle rozważać? Otóż wyobraźmy sobie, że wszystkie zbiory określonej mocy mają jakąś cechę (np. spośród zbioru pól na szachownicy można wybrać n takich pól, że, postawiwszy na nich wieże, nie atakują się one parami). Jeśli odpowiedź na nurtujące pytanie jest twierdząca możemy powiedzieć natychmiastowo, że wszystkie zbiory mocy o 1 większej też mają tę cechę.
Można mówić o genetyce zbiorów, o dziedziczeniu pewnych cech z rodziny zbiorów pewnej mocy na rodzinę zbiorów o mocy większej o 1.
Do tej pory ustaliłem, że zachodzi:
dla \(\displaystyle{ t<n-k}\) : nie
dla \(\displaystyle{ t>\frac{(n-k)^{2}}{4}}\) : tak
Jednak wynik nie zachwyca bo "luka" przypadków nierozstrzygniętych rośnie kwadratowo wraz z \(\displaystyle{ (n-k)}\) więc tylko w nietypowych sytuacjach mamy zadowalające rezultaty.
Ostatnio zmieniony 14 wrz 2011, o 21:58 przez Qń, łącznie zmieniany 1 raz.
Powód: Poprawa nieregulaminowej nazwy tematu.
Powód: Poprawa nieregulaminowej nazwy tematu.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
Rozwazania moze ulatwic nastepujaca obserwacja.
Z takiej szachownicy robimy macierz \(\displaystyle{ n\times n}\), nazwijmy ja \(\displaystyle{ M}\). Niech
\(\displaystyle{ \mathbf{1}=\begin{pmatrix}1\\1\\\vdots\\1\end{pmatrix}}\)
będzie wektorem jedynek.
Z szachownicy nie można niczego wywalić wtedy i tylko wtedy, gdy
\(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
Po otworzeniu nawiasow i zinterpretowaniu \(\displaystyle{ M}\) jako macierzy sąsiedztwa pewnego grafu skierowanego (tutaj każdy wierzchołek ma przynajmniej \(\displaystyle{ k}\) sąsiadów, lub jest sąsiadem przynajmniej \(\displaystyle{ k}\) wierzcholkow) prawa strona wyrażenia powyżej to:
\(\displaystyle{ nL_2-2kL_1+nk^2}\)
gdzie \(\displaystyle{ L_i}\) to liczba dróg długości \(\displaystyle{ i}\) w tym grafie.
Jeśli \(\displaystyle{ k}\) dzieli \(\displaystyle{ n}\), to chyba potrafię wskazać taki nieredukowalny układ z
\(\displaystyle{ \frac{n(k+1)}2}\)
jedynkami. Jeśli nie dzieli, to podobnie.
Z takiej szachownicy robimy macierz \(\displaystyle{ n\times n}\), nazwijmy ja \(\displaystyle{ M}\). Niech
\(\displaystyle{ \mathbf{1}=\begin{pmatrix}1\\1\\\vdots\\1\end{pmatrix}}\)
będzie wektorem jedynek.
Z szachownicy nie można niczego wywalić wtedy i tylko wtedy, gdy
\(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
Po otworzeniu nawiasow i zinterpretowaniu \(\displaystyle{ M}\) jako macierzy sąsiedztwa pewnego grafu skierowanego (tutaj każdy wierzchołek ma przynajmniej \(\displaystyle{ k}\) sąsiadów, lub jest sąsiadem przynajmniej \(\displaystyle{ k}\) wierzcholkow) prawa strona wyrażenia powyżej to:
\(\displaystyle{ nL_2-2kL_1+nk^2}\)
gdzie \(\displaystyle{ L_i}\) to liczba dróg długości \(\displaystyle{ i}\) w tym grafie.
Jeśli \(\displaystyle{ k}\) dzieli \(\displaystyle{ n}\), to chyba potrafię wskazać taki nieredukowalny układ z
\(\displaystyle{ \frac{n(k+1)}2}\)
jedynkami. Jeśli nie dzieli, to podobnie.
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
Szczerze to nie znam się na teorii grafów bo jeszcze tego nie brałem.
\(\displaystyle{ n \cdot k \le \frac{n(k+1)}2 \Leftrightarrow n \cdot k \le 1 \Leftrightarrow n=k=1}\)
Ale zauważ, że każda taka macierz ma w sumie minimum \(\displaystyle{ n \cdot k}\). Zatem sprawdźmy kiedy możesz stworzyć układ z \(\displaystyle{ \frac{n(k+1)}2}\):xiikzodz pisze: Jeśli \(\displaystyle{ k}\) dzieli \(\displaystyle{ n}\), to chyba potrafię wskazać taki nieredukowalny układ z
\(\displaystyle{ \frac{n(k+1)}2}\)
jedynkami. Jeśli nie dzieli, to podobnie.
\(\displaystyle{ n \cdot k \le \frac{n(k+1)}2 \Leftrightarrow n \cdot k \le 1 \Leftrightarrow n=k=1}\)
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
Mój poprzedni post omyłkowo dotyczył minimalnie innego (znacznie trudniejszego) zagadnienia, co jest wynikiem niedoczytania treści na niewygodnym w obsłudze urządzeniu. Ale zagadnienie jest dość pokrewne.
Poprawka. Przy oznaczeniach z mojego poprzedniego postu szukamy takich zero-jedynkowych \(\displaystyle{ n\times n}\) macierzy \(\displaystyle{ M}\), że wektory
\(\displaystyle{ M\mathbf{1}-k\mathbf{1}}\)
\(\displaystyle{ \left(\mathbf{1^T}M\right)^T-k\mathbf{1}}\)
mają nieujemne współrzędne oraz
\(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
Analogiczna poprawka w języku grafów. Rozważamy skierowane grafy (z pętelkami) o \(\displaystyle{ n}\) wierzchołkach takie, że każdy wierzchołek jest sąsiadem co najmniej \(\displaystyle{ k}\) wierzchołków i ma co najmniej \(\displaystyle{ k}\) sąsiadów. Szukamy takich grafów, że:
\(\displaystyle{ nL_2-2kL_1+nk^2=0}\).
Muszę wyjść, ale po powrocie dopiszę, co z tego wynika dla liczby jedynek w macierzy.
Poprawka. Przy oznaczeniach z mojego poprzedniego postu szukamy takich zero-jedynkowych \(\displaystyle{ n\times n}\) macierzy \(\displaystyle{ M}\), że wektory
\(\displaystyle{ M\mathbf{1}-k\mathbf{1}}\)
\(\displaystyle{ \left(\mathbf{1^T}M\right)^T-k\mathbf{1}}\)
mają nieujemne współrzędne oraz
\(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
Analogiczna poprawka w języku grafów. Rozważamy skierowane grafy (z pętelkami) o \(\displaystyle{ n}\) wierzchołkach takie, że każdy wierzchołek jest sąsiadem co najmniej \(\displaystyle{ k}\) wierzchołków i ma co najmniej \(\displaystyle{ k}\) sąsiadów. Szukamy takich grafów, że:
\(\displaystyle{ nL_2-2kL_1+nk^2=0}\).
Muszę wyjść, ale po powrocie dopiszę, co z tego wynika dla liczby jedynek w macierzy.
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
Mnożysz nadwyżkę jedynek w i-tym wierszu przez nadwyżkę jedynek w i-tej kolumnie macierzy M i sumujesz po i=1,...,n. Ale co ci to daje? Jeśli nawet wyjdzie wynik dodatni to o niczym to nie świadczy. Bo weźmy i-ty wiersz oraz i-tą kolumnę. Nawet jeśli w obu jest nadwyżka jedynek to przecież na ich przecięciu - pozycja (i,i) - może jedynki żadnej nie być więc ten warunek wcale nie musi być spełniony.xiikzodz pisze: \(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
Jeśli z macierzy nie można usunąć jedynki na pozycji \(\displaystyle{ i,j}\) to znaczy, że w \(\displaystyle{ i}\)-tym wierszu lub w \(\displaystyle{ j}\)-tej kolumnie jest dokładnie \(\displaystyle{ k}\) jedynek, czyli iloczyn nadwyżek wynosi zero. I na odwrót. Stąd równanie.
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
Nieprawda właśnie. weźmy n=4, k=2. Niech w pierwszym wiersz będzie od lewej do prawej (1,1,1,0) a w czwartek kolumnie z góry na dół (0,1,1,1). I ten wiersza i ta kolumna mają nadwyżkę (\(\displaystyle{ 3>k=2}\) a mimo to nie można nic usunąć z pozycji (1,4) bo tam jest zero.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
Faktycznie. To znaczy żeby zepsuć argument wystarczy wziąć:
\(\displaystyle{ \begin{pmatrix}0&1&1&1\\1&0&0&1\\1&0&1&0\\1&1&0&0\end{pmatrix}}\).
OK, jeszcze jedna próba zapisania tego macierzowo. Jedynki z pozycji \(\displaystyle{ i,j}\) nie można usunąć, wtedy, i tylko wtedy, gdy w \(\displaystyle{ i}\)-tym wierszu, lub w \(\displaystyle{ j}\)-tej kolumnie jest dokładnie \(\displaystyle{ k}\) jedynek. Niech \(\displaystyle{ w_i}\) będzie liczbą jedynek w \(\displaystyle{ i}\)-tym wierszu, zaś \(\displaystyle{ k_i}\) liczbą jedynek w \(\displaystyle{ i}\)-tej kolumnie macierzy \(\displaystyle{ M=(m_{ij})}\). Z macierzy nie można usunąć żadnej jedynki wtedy i tylko wtedy, gdy \(\displaystyle{ \sum_{i,j}w_ik_jm_{ij}=0}\).
\(\displaystyle{ \begin{pmatrix}0&1&1&1\\1&0&0&1\\1&0&1&0\\1&1&0&0\end{pmatrix}}\).
OK, jeszcze jedna próba zapisania tego macierzowo. Jedynki z pozycji \(\displaystyle{ i,j}\) nie można usunąć, wtedy, i tylko wtedy, gdy w \(\displaystyle{ i}\)-tym wierszu, lub w \(\displaystyle{ j}\)-tej kolumnie jest dokładnie \(\displaystyle{ k}\) jedynek. Niech \(\displaystyle{ w_i}\) będzie liczbą jedynek w \(\displaystyle{ i}\)-tym wierszu, zaś \(\displaystyle{ k_i}\) liczbą jedynek w \(\displaystyle{ i}\)-tej kolumnie macierzy \(\displaystyle{ M=(m_{ij})}\). Z macierzy nie można usunąć żadnej jedynki wtedy i tylko wtedy, gdy \(\displaystyle{ \sum_{i,j}w_ik_jm_{ij}=0}\).
Ostatnio zmieniony 21 wrz 2011, o 23:31 przez xiikzodz, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
no dobra ale wciąż rozważasz tylko pary: i-ty wiersz oraz i-ta kolumna. A przecież redukcja może zajść na pozycji (i,j) gdzie \(\displaystyle{ i \neq j}\).
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
Aj, zamiast \(\displaystyle{ \sum_{i,j}w_ik_jm_{ij}=0}\) miało być:
\(\displaystyle{ \sum_{i,j}(w_i-k)(k_j-k)m_{ij}=0}\), co można zapisać w formie:
Jeśli
\(\displaystyle{ T=(t_{ij})=(M\mathbf{1}-k\mathbf{1})(\mathbf{1}^TM-k\mathbf{1}^T)}\),
to
dla każdych \(\displaystyle{ i,j}\):
\(\displaystyle{ t_{ij}m_{ij}=0}\).
\(\displaystyle{ \sum_{i,j}(w_i-k)(k_j-k)m_{ij}=0}\), co można zapisać w formie:
Jeśli
\(\displaystyle{ T=(t_{ij})=(M\mathbf{1}-k\mathbf{1})(\mathbf{1}^TM-k\mathbf{1}^T)}\),
to
dla każdych \(\displaystyle{ i,j}\):
\(\displaystyle{ t_{ij}m_{ij}=0}\).
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
zgadzam się z tą równością. być może idzie to dalej wykorzystać w dobrym kierunku. ja na razie myślę w trochę inną stronę i zobaczę, czy do czegoś mnie to doprowadzi.
Ostatnio zmieniony 22 wrz 2011, o 00:00 przez MichalKulis, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Zbiór pól na szachownicy.
\(\displaystyle{ T=(M\mathbf{1}-k\mathbf{1})(\mathbf{1}^TM-k\mathbf{1}^T)}\)
Jeszcze coś takiego można z tych macierzy zobaczyć.
Jeśli \(\displaystyle{ R}\) to liczba wierszy, a \(\displaystyle{ C}\) to liczba kolumn z dokładnie \(\displaystyle{ k}\) jedynkami, wówczas mamy szacowanie liczby \(\displaystyle{ N}\) jedynek w "nieredukowalnej" macierzy \(\displaystyle{ M}\):
\(\displaystyle{ N\le n(R+C)-RC}\)
Jeszcze coś takiego można z tych macierzy zobaczyć.
Jeśli \(\displaystyle{ R}\) to liczba wierszy, a \(\displaystyle{ C}\) to liczba kolumn z dokładnie \(\displaystyle{ k}\) jedynkami, wówczas mamy szacowanie liczby \(\displaystyle{ N}\) jedynek w "nieredukowalnej" macierzy \(\displaystyle{ M}\):
\(\displaystyle{ N\le n(R+C)-RC}\)
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
-
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Zbiór pól na szachownicy.
to jest ciekawe ograniczenie.
-- 22 wrz 2011, o 08:58 --
Dobra, mam rozwiązanie.
Zanim co, najpierw ponowię treść problemu w nieco zwięźlejszy sposób.
Mamy rodzinę zero-jedynkowych macierzy \(\displaystyle{ n \cdot n}\) o tej własności, że suma składników w każdym wierszu i każdej kolumnie jest \(\displaystyle{ \ge k}\).
Przez moc macierzy rozumiemy sumę jej wszystkich składników.
Przez macierz redukowalną rozumiemy macierz, w której jest choć jedna "jedynka", która można zamienić na "zero" i dalej będziemy mieli macierz z naszej rodziny (tj. taką, która spełnia naszą własność).
Zadanie: znaleźć największą macierz (w sensie mocy) nieredukowalną. Rozpatrujemy tylko przypadki nietrywialne, czyli: \(\displaystyle{ 0<k<n}\)
Rozwiązanie:
M - nasza potencjalna macierz nieredukowalna
\(\displaystyle{ n \cdot k \le \left| M\right| \le n \cdot n}\)
Przed nadwyżkę \(\displaystyle{ t}\) mocy rozumiem \(\displaystyle{ t = \left| M\right| - n \cdot k}\)
Niech E= zbiór wierszy o sumie składników \(\displaystyle{ >k}\)
Niech F= zbiór kolumn o sumie składników \(\displaystyle{ >k}\)
Niech \(\displaystyle{ x = \left| E\right|}\)
Niech \(\displaystyle{ y= \left| F\right|}\)
\(\displaystyle{ E = \left\{ {e_{i}} : i=1,2,...,x}\right\}}\) gdzie \(\displaystyle{ e _{i}}\) oznacza nadwyżkę mocy w i-tym wierszu
\(\displaystyle{ F= \left\{ {f _{j}} : j=1,2,...,y}\right\}}\) gdzie \(\displaystyle{ f _{j}}\) oznacza nadwyżkę mocy w j-tej kolumnie
Popatrzmy na wiersze i kolumny z E i F. Suma składników w każdym z nich musi spełniać:
\(\displaystyle{ k + e _{i} \le n - y}\)
\(\displaystyle{ k + f _{j} \le n - x}\)
Dlaczego tak? Bo na przecięciu wierszy z E i kolumn z F muszą być same zera - w p.p. macierz jest redukowalna.
\(\displaystyle{ e _{i} \le n-k-y}\)
\(\displaystyle{ f _{j} \le n-k-x}\)
\(\displaystyle{ max(E) \le n-k-y}\)
\(\displaystyle{ max(F) \le n-k-x}\)
Jasnym jest, że \(\displaystyle{ \sum_{i=1}^{x}e _{i} = t}\) oraz \(\displaystyle{ \sum_{j=1}^{y}f _{j} = t}\).
Zatem jeśli mamy pewne ustalone wartości x,y to najlepiej jest rozmieścić nadwyżkę mocy \(\displaystyle{ t}\) równomiernie w wierszach z \(\displaystyle{ E}\) i w kolumnach z \(\displaystyle{ F}\) tak, aby maksymalny element był jak najmniejszy.Czyli np. \(\displaystyle{ t=13, x=4}\). Zatem \(\displaystyle{ E={4,3,3,3}}\). Zatem:
\(\displaystyle{ \lceil \frac{t}{x} \rceil \le n-k-y}\)
\(\displaystyle{ \lceil \frac{t}{y} \rceil \le n-k-x}\)
\(\displaystyle{ t \le x \cdot (n-k-y)}\)
\(\displaystyle{ t \le y \cdot (n-k-x)}\)
Dla ułatwienia rachunków podstawmy: \(\displaystyle{ n-k=b}\) przy czym \(\displaystyle{ 0 < b < n}\). Ponadto pamiętajmy, że \(\displaystyle{ 1 \le x \le t, 1 \le y \le t}\) oraz \(\displaystyle{ x < b, y < b}\).
\(\displaystyle{ t \le x \cdot (b-y)}\)
\(\displaystyle{ t \le y \cdot (b-x)}\)
\(\displaystyle{ x \ge \frac{t}{b-y}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
Teraz dopiszemy trzecią nierówność pomocniczą, która wynika z tych dwóch.
\(\displaystyle{ x \ge \frac{t}{b-y}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
\(\displaystyle{ x \ge \frac{t}{b- \frac{t}{b-x}}}\)
\(\displaystyle{ y \le b - \frac{t}{x}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
\(\displaystyle{ -bx^{2} + b^{2} - bt \ge 0}\)
\(\displaystyle{ \frac{t}{b-x} \le y \le b - \frac{t}{x}}\)
\(\displaystyle{ \Delta = b^{2} \cdot (b^{2} - 4t)}\)
\(\displaystyle{ \frac{t}{b-x} \le y \le b - \frac{t}{x}}\)
\(\displaystyle{ x \in \left[ x _{1},x _{2} \right]}\)
Z tego układu warunków otrzymujemy potencjalne pary (x,y) - uwaga na ograniczenia, które wcześniej podałem!
Teraz (wiedząc, jakie mają być sumy składników we wszystkich wierszach i wszystkich kolumnach) trzeba tylko sprawdzić, czy jesteśmy w stanie odpowiednio wypełnić tą macierz. Dzieje się tak jeśli:
\(\displaystyle{ k + \lceil \frac{t}{x} \rceil \le n -y \Leftrightarrow \lceil \frac{t}{x} \rceil \le b - y}\) a to już sprawdziliśmy po drodze!
Podsumowując, procedura jest następująca: wybieramy największe \(\displaystyle{ t}\) tak aby \(\displaystyle{ \Delta \ge 0}\). Sprawdzamy potencjalne pary (x,y). Istnienie choć jednej z nich gwarantuje sukces. Jeśli nie ma żadnych to zmniejszamy t o 1 i szukamy ponownie par (x,y) spełniających wszystkie kryteria.-- 26 wrz 2011, o 00:34 --@xiikzodz - a co to jest to trudniejsze, pokrewne zagadnienie?
-- 22 wrz 2011, o 08:58 --
Dobra, mam rozwiązanie.
Zanim co, najpierw ponowię treść problemu w nieco zwięźlejszy sposób.
Mamy rodzinę zero-jedynkowych macierzy \(\displaystyle{ n \cdot n}\) o tej własności, że suma składników w każdym wierszu i każdej kolumnie jest \(\displaystyle{ \ge k}\).
Przez moc macierzy rozumiemy sumę jej wszystkich składników.
Przez macierz redukowalną rozumiemy macierz, w której jest choć jedna "jedynka", która można zamienić na "zero" i dalej będziemy mieli macierz z naszej rodziny (tj. taką, która spełnia naszą własność).
Zadanie: znaleźć największą macierz (w sensie mocy) nieredukowalną. Rozpatrujemy tylko przypadki nietrywialne, czyli: \(\displaystyle{ 0<k<n}\)
Rozwiązanie:
M - nasza potencjalna macierz nieredukowalna
\(\displaystyle{ n \cdot k \le \left| M\right| \le n \cdot n}\)
Przed nadwyżkę \(\displaystyle{ t}\) mocy rozumiem \(\displaystyle{ t = \left| M\right| - n \cdot k}\)
Niech E= zbiór wierszy o sumie składników \(\displaystyle{ >k}\)
Niech F= zbiór kolumn o sumie składników \(\displaystyle{ >k}\)
Niech \(\displaystyle{ x = \left| E\right|}\)
Niech \(\displaystyle{ y= \left| F\right|}\)
\(\displaystyle{ E = \left\{ {e_{i}} : i=1,2,...,x}\right\}}\) gdzie \(\displaystyle{ e _{i}}\) oznacza nadwyżkę mocy w i-tym wierszu
\(\displaystyle{ F= \left\{ {f _{j}} : j=1,2,...,y}\right\}}\) gdzie \(\displaystyle{ f _{j}}\) oznacza nadwyżkę mocy w j-tej kolumnie
Popatrzmy na wiersze i kolumny z E i F. Suma składników w każdym z nich musi spełniać:
\(\displaystyle{ k + e _{i} \le n - y}\)
\(\displaystyle{ k + f _{j} \le n - x}\)
Dlaczego tak? Bo na przecięciu wierszy z E i kolumn z F muszą być same zera - w p.p. macierz jest redukowalna.
\(\displaystyle{ e _{i} \le n-k-y}\)
\(\displaystyle{ f _{j} \le n-k-x}\)
\(\displaystyle{ max(E) \le n-k-y}\)
\(\displaystyle{ max(F) \le n-k-x}\)
Jasnym jest, że \(\displaystyle{ \sum_{i=1}^{x}e _{i} = t}\) oraz \(\displaystyle{ \sum_{j=1}^{y}f _{j} = t}\).
Zatem jeśli mamy pewne ustalone wartości x,y to najlepiej jest rozmieścić nadwyżkę mocy \(\displaystyle{ t}\) równomiernie w wierszach z \(\displaystyle{ E}\) i w kolumnach z \(\displaystyle{ F}\) tak, aby maksymalny element był jak najmniejszy.Czyli np. \(\displaystyle{ t=13, x=4}\). Zatem \(\displaystyle{ E={4,3,3,3}}\). Zatem:
\(\displaystyle{ \lceil \frac{t}{x} \rceil \le n-k-y}\)
\(\displaystyle{ \lceil \frac{t}{y} \rceil \le n-k-x}\)
\(\displaystyle{ t \le x \cdot (n-k-y)}\)
\(\displaystyle{ t \le y \cdot (n-k-x)}\)
Dla ułatwienia rachunków podstawmy: \(\displaystyle{ n-k=b}\) przy czym \(\displaystyle{ 0 < b < n}\). Ponadto pamiętajmy, że \(\displaystyle{ 1 \le x \le t, 1 \le y \le t}\) oraz \(\displaystyle{ x < b, y < b}\).
\(\displaystyle{ t \le x \cdot (b-y)}\)
\(\displaystyle{ t \le y \cdot (b-x)}\)
\(\displaystyle{ x \ge \frac{t}{b-y}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
Teraz dopiszemy trzecią nierówność pomocniczą, która wynika z tych dwóch.
\(\displaystyle{ x \ge \frac{t}{b-y}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
\(\displaystyle{ x \ge \frac{t}{b- \frac{t}{b-x}}}\)
\(\displaystyle{ y \le b - \frac{t}{x}}\)
\(\displaystyle{ y \ge \frac{t}{b-x}}\)
\(\displaystyle{ -bx^{2} + b^{2} - bt \ge 0}\)
\(\displaystyle{ \frac{t}{b-x} \le y \le b - \frac{t}{x}}\)
\(\displaystyle{ \Delta = b^{2} \cdot (b^{2} - 4t)}\)
\(\displaystyle{ \frac{t}{b-x} \le y \le b - \frac{t}{x}}\)
\(\displaystyle{ x \in \left[ x _{1},x _{2} \right]}\)
Z tego układu warunków otrzymujemy potencjalne pary (x,y) - uwaga na ograniczenia, które wcześniej podałem!
Teraz (wiedząc, jakie mają być sumy składników we wszystkich wierszach i wszystkich kolumnach) trzeba tylko sprawdzić, czy jesteśmy w stanie odpowiednio wypełnić tą macierz. Dzieje się tak jeśli:
\(\displaystyle{ k + \lceil \frac{t}{x} \rceil \le n -y \Leftrightarrow \lceil \frac{t}{x} \rceil \le b - y}\) a to już sprawdziliśmy po drodze!
Podsumowując, procedura jest następująca: wybieramy największe \(\displaystyle{ t}\) tak aby \(\displaystyle{ \Delta \ge 0}\). Sprawdzamy potencjalne pary (x,y). Istnienie choć jednej z nich gwarantuje sukces. Jeśli nie ma żadnych to zmniejszamy t o 1 i szukamy ponownie par (x,y) spełniających wszystkie kryteria.-- 26 wrz 2011, o 00:34 --@xiikzodz - a co to jest to trudniejsze, pokrewne zagadnienie?