Zbiór pól na szachownicy.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

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.
Ostatnio zmieniony 14 wrz 2011, o 21:58 przez , łącznie zmieniany 1 raz.
Powód: Poprawa nieregulaminowej nazwy tematu.
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

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.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

Szczerze to nie znam się na teorii grafów bo jeszcze tego nie brałem.
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.
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}\):

\(\displaystyle{ n \cdot k \le \frac{n(k+1)}2 \Leftrightarrow n \cdot k \le 1 \Leftrightarrow n=k=1}\)
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

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.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

xiikzodz pisze: \(\displaystyle{ \left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0}\).
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
Użytkownik
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.

Post autor: xiikzodz »

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.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

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.
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

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}\).
Ostatnio zmieniony 21 wrz 2011, o 23:31 przez xiikzodz, łącznie zmieniany 1 raz.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

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}\).
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

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}\).
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

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.
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

\(\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}\)
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

skąd ten wzór?
xiikzodz
Użytkownik
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.

Post autor: xiikzodz »

Wśród liczb \(\displaystyle{ m_{ij}}\) nie może być więcej jedynek, niż wśród liczb \(\displaystyle{ (w_i-k)(k_j-k)}\) zer.
MichalKulis
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 19 sty 2011, o 08:15
Płeć: Mężczyzna
Lokalizacja: Wrocław

Zbiór pól na szachownicy.

Post autor: MichalKulis »

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?
ODPOWIEDZ