szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 13:51 
Użytkownik

Posty: 18
Lokalizacja: Łódź
Jak zliczyć ilość macierzy wymiaru 5x5, której elementy są 0 lub 1 i:
1. element a _{i,i} jest zawsze = 0
2. każdy wiersz i każda kolumna ma 2 jedynki i 3 zera
3. a _{i,j} \neq a _{j,i}?
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 16:15 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
Ile masz miejsc już znanych, a ile do obsadzenia. Na ile sposobów można obstawić każde z nich?
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 16:53 
Użytkownik

Posty: 18
Lokalizacja: Łódź
Średnio pomaga mi ta podpowiedź. Znam całą przekątną bo wynosi 0. Jeśli w pierwszym wierszu postawie 2 zera (równoważnie 2 jedynki) to możliwości takich jest 6 (4 po 2). Automatycznie wypełniam w ten sposób pierwszą kolumnę. Później możliwości mamy 3 (3 po 2).
Nie wiem natomiast jak rozpatrzyć dalszą część. Wszystko zależy czy wypełniamy kolumnę która posiada już jedynkę czy nie...
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 17:06 
Użytkownik

Posty: 7361
Lokalizacja: Z Bielskia-Białej
Na ile sposobów obstawisz jedno pole?

-- 12 listopada 2015, 17:13 --

To są trzy podpunkty czy trzy warunki do spełnienia jednocześnie?
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 18:49 
Użytkownik

Posty: 18
Lokalizacja: Łódź
Warunki są do spełnienia jednoczesnie
Góra
Mężczyzna Offline
PostNapisane: 12 lis 2015, o 19:28 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: blisko
Ja bym ci radził ułożyć układ 10 równań z 20 niewiadomymi trochę liczenia ale do przejścia,
Wyliczyć co się da a potem zaostrzyć na trzeci warunek.
Każda niewiadoma przyjmuje wartość jeden lub zero!

0+x_{1,2}+...+x_{1,5}=2

x_{2,1}+0+...+x_{2,5}=2

....................................

x_{5,1}+x_{5,2}+...+0=2

A potem kolumny:

...............................................................


Po redukcji otrzymasz:

\left(  x_{1,2}+x_{2,1}\right) +\left(  x_{1,3}+x_{3,1}\right) +...+\left(  x_{3,4}+x_{4,3}\right)+x_{5,1}+x_{5,2}+x_{5,3}=8

Sumy w nawiasach wynoszą jeden z warunków zadania

Nawiasów masz sześć plus ostanie trzy składniki dowolne

Zredukuje się równanie do:

x_{5,1}+x_{5,2}+x_{5,3}=2

Jak widać masz trzy przypadki, któreś z nich musi być zero!

I tak dalej redukuj sobie i sprawdzaj!

Zresztą masz jeszcze:

x_{i,j}+x_{j,i}=1




Sprowadziło mi się to do dwóch niezależnych równań:

x_{1,2}+x_{1,3}+\left( x_{1,4}+x_{1,5}\right)=2

x_{2,4}+x_{3,4}+ x_{2,5}+x_{3,5}+\left( x_{1,4}+x_{1,5}\right)=2

I wszystko sprowadza się do policzenia ilości tych równań co nie jest trudne.


Suma w nawiasie może być równa:

0,1,2


Co daje 20 możliwości!
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2015, o 21:07 
Użytkownik

Posty: 18
Lokalizacja: Łódź
Wynik się nie zgadza, brakuje 4 macierzy
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2015, o 13:17 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: blisko
Sprawdź jeszcze dokładnie rozwiąż sobie ten układ równań bo rzeczywiście mogłem się gdzieś walnąć w rachunkach!
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2015, o 20:12 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Byłby to skandal, gdyby wynik nie dzielił się przez 6. Wynik jest równy sześć razy liczba możliwych uzupełnień macierzy:

\begin{pmatrix}
0 & 0 & 0 & 1 & 1 \\
1 & 0 & ? & ? & ? \\
1 & ? & 0 & ? & ? \\
0 & ? & ? & 0 & ? \\
0 & ? & ? & ? & 0 
\end{pmatrix}.

Ostatecznie wychodzi na to, że wszystkie rozwiązania są takie same z dokładnością do jednoczesnej permutacji wierszy i kolumn.
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2015, o 22:52 
Użytkownik
Avatar użytkownika

Posty: 3500
Lokalizacja: blisko
Podsumowanie:

a+b=x_{1,2}+x_{1,4}=2-x_{1,3}-x_{1,5}

A+B=x_{2,5}+x_{4,5}=2-x_{3,5}-x_{1,5}

x-y= x_{3,4}+x_{2,3}=2-x_{1,3}-x_{3,5}


oraz:

1+x_{4,5}-x_{1,4}-x_{3,4}=x_{2,4}=0  \vee  1

co generalnie daje nam dwa równania:

x_{1,4}+x_{3,4}=x_{4,5}

lub:

x_{1,4}+x_{3,4}=1+x_{4,5}


w wersji uproszczonej:

b+x=B

lub:

b+x=1+B


Biorąc do kupy:

a+b=2-x_{1,3}-x_{1,5}

A+B=2-x_{3,5}-x_{1,5}

x-y=2-x_{1,3}-x_{3,5}

oraz:

(*) b+x=B   \vee b+x=1+B

Teraz nic nie zostaje jak liczyć przypadki:

I. (x_{1,3},x_{1,5},x_{3,5})=(0,0,0)

wtedy:

a+b=2

A+B=2

x-y=0 -, oraz (*) mamy dwa rozwiązania


II. (x_{1,3},x_{1,5},x_{3,5})=(0,1,0)

wtedy:

a+b=1

A+B=1

x-y=0 -, oraz (*) mamy 6 rozwiązań łatwo sprawdzić


III. (x_{1,3},x_{1,5},x_{3,5})=(0,0,1)

wtedy:

a+b=2

A+B=1

x-y=1 -, oraz (*) mamy 2 rozwiązania


IV. (x_{1,3},x_{1,5},x_{3,5})=(0,1,1)

wtedy:

a+b=1

A+B=0

x-y=-1 -, oraz (*) mamy 2 rozwiązania


V. (x_{1,3},x_{1,5},x_{3,5})=(1,0,1)

wtedy:

a+b=1

A+B=1

x-y=1 -, oraz (*) mamy 6 rozwiązań


VI. (x_{1,3},x_{1,5},x_{3,5})=(1,1,0)

wtedy:

a+b=0

A+B=1

x-y=1 -, oraz (*) mamy 2 rozwiązania


VII. (x_{1,3},x_{1,5},x_{3,5})=(1,0,0)

wtedy:

a+b=1

A+B=2

x-y=1 -, oraz (*) mamy 2 rozwiązania


VIII. (x_{1,3},x_{1,5},x_{3,5})=(1,1,1)

wtedy:

a+b=0

A+B=0

x-y=0 -, oraz (*) mamy 2 rozwiązania


Razem daje:

2+6+2+2+6+2+2+2=24 - rozwiązania

Już nie będzie skandalu!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 rekurencja, zliczanie ciągów  kolegasafeta  4
 Zliczanie zbiorów - zadanie 4  bolt24  1
 Wartości własne macierzy przyległości - zadanie 2  biksu  2
 Zliczanie podziałów liczb  matinf  13
 Zliczanie wierzchołków i krawędzi grafu planarnego  emperor2  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl