czy mógłby ktoś pomoc rozwiązać 4 zadania z matematyki dyskretnej i krótko wytłumaczyć?
Zad. 1
Z biało-czarnej pokratkowanej tablicy wymiaru n x n osunięto dwa kwadraty. Pokazać, ze pozostala czesc tablicy może być pokryta nie nakladajacymi sie kostkami domina wtedy u tylko wtedy, gdy n jest parzyste i dwa usunięte kwadraty sa roznych kolorow.
zad. 2
Niech G bedzie grafem na 2d+1 wierzcholkach, z ktorych kazdy ma stopien d. Pokazac, ze G jest eulerowski.
zad 3.
Grupa skadajaca sie z n osob ustawia sie losowo w kolejce. Obliczyc prawdopodobienstwo, ze pomiedzy dwoma z gory ustalonymi osobami bedzie stalo dokladnie r osob (r ≤ n-2)
zad. 4
Na podstawie zaleznosci rekurencyjnej (5.7) udowodnic rownanie
\(\displaystyle{ D_{n}}\)=n\(\displaystyle{ D_{n-1}}\) +\(\displaystyle{ (-1)^{n}}\)
\(\displaystyle{ n qslant 1}\)
(5.7) tresc tegoz zadania brzmi:
Znalezc rownanie rekurencyjne dla liczby g*(n,k) k-elementowych podzbiorow zbioru [n] bez sasiadow modulo n.
za pomoc wielce dziekuje.
Grafy; tablica n na n; n osób w kolejce; rekurencja.
-
- Użytkownik
- Posty: 5
- Rejestracja: 15 sty 2008, o 13:09
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 3 razy
Grafy; tablica n na n; n osób w kolejce; rekurencja.
moze dodam, ze zupelnie nie rozumiem matematyki dyskretnej i czy moglby ktos poprostu podac rozwiazanie zadania
-
- Użytkownik
- Posty: 2826
- Rejestracja: 30 gru 2006, o 20:38
- Płeć: Kobieta
- Lokalizacja: Lublin/warszawa
- Podziękował: 62 razy
- Pomógł: 482 razy
Grafy; tablica n na n; n osób w kolejce; rekurencja.
Mając wskazówkę, wystarczyło tylko chwilę pomyśleć...
Kostka domina pokrywa dokładnie dwa pola. Czyli k kostek pokrywa dokładnie 2k pól. Ponieważ kwadrat liczby nieparzystej jest liczbą nieparzystą, to jeśli n jest nieparzyste, to liczba pól również jest nieparzysta. Czyli n musi być parzyste.
Zatem n jest parzyste, czyli masz \(\displaystyle{ \frac{1}{2}n^2}\) pól białych i \(\displaystyle{ \frac{1}{2}n^2}\) pól czarnych. Ponieważ kostka pokrywa jedno takie i jedno takie pole, to aby po usunięciu dwóch pól dało się pokryć tablicę, usunięte pola muszą być różnych kolorów.
Kostka domina pokrywa dokładnie dwa pola. Czyli k kostek pokrywa dokładnie 2k pól. Ponieważ kwadrat liczby nieparzystej jest liczbą nieparzystą, to jeśli n jest nieparzyste, to liczba pól również jest nieparzysta. Czyli n musi być parzyste.
Zatem n jest parzyste, czyli masz \(\displaystyle{ \frac{1}{2}n^2}\) pól białych i \(\displaystyle{ \frac{1}{2}n^2}\) pól czarnych. Ponieważ kostka pokrywa jedno takie i jedno takie pole, to aby po usunięciu dwóch pól dało się pokryć tablicę, usunięte pola muszą być różnych kolorów.
- kinwotar
- Użytkownik
- Posty: 91
- Rejestracja: 30 sty 2007, o 21:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 21 razy
Grafy; tablica n na n; n osób w kolejce; rekurencja.
z. 3.
\(\displaystyle{ \frac{2(n-r-1)(n-2)!}{n!}}\) bo:
* moc omegi rowna jest n!
*wybierasz najpierw dwie osoby które mogą sie zamienic miejscami stąd ta dwójka
*n-r-1 jest to liczba możliwych pozycji tych dwóch osób i r osób między nimi w n elementowym ciągu
*(n-2)! tyle jest możliwości przestawień pozostaych ludzi poza wybraną dwójką.
\(\displaystyle{ \frac{2(n-r-1)(n-2)!}{n!}}\) bo:
* moc omegi rowna jest n!
*wybierasz najpierw dwie osoby które mogą sie zamienic miejscami stąd ta dwójka
*n-r-1 jest to liczba możliwych pozycji tych dwóch osób i r osób między nimi w n elementowym ciągu
*(n-2)! tyle jest możliwości przestawień pozostaych ludzi poza wybraną dwójką.
-
- Użytkownik
- Posty: 185
- Rejestracja: 6 maja 2006, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 32 razy
Grafy; tablica n na n; n osób w kolejce; rekurencja.
Ad. 2. to prosciutko:
z def. => graf eulerowski spojny i stopien kazdego wierzcholka parzysty.
2d+1 to liczba nieparzysta
suma stopni wierzcholkow grafu jest 2 razy wieksza od sumy krawedzi (chyba oczywiste)
wiec suma stopni wierzcholkow jest parzysta (2E jest podzielne przez 2)
wuec gdyby d bylo nieparzyste, to d*(2d+1) tez byloby nie parzyste, bo iloczyn licz nieparzystych jest nieparzysty => dostajemy sprzecznosc, a zatem d musi byc parzyste => graf jest eulerowski
z def. => graf eulerowski spojny i stopien kazdego wierzcholka parzysty.
2d+1 to liczba nieparzysta
suma stopni wierzcholkow grafu jest 2 razy wieksza od sumy krawedzi (chyba oczywiste)
wiec suma stopni wierzcholkow jest parzysta (2E jest podzielne przez 2)
wuec gdyby d bylo nieparzyste, to d*(2d+1) tez byloby nie parzyste, bo iloczyn licz nieparzystych jest nieparzysty => dostajemy sprzecznosc, a zatem d musi byc parzyste => graf jest eulerowski
-
- Użytkownik
- Posty: 5
- Rejestracja: 15 sty 2008, o 13:09
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 3 razy
Grafy; tablica n na n; n osób w kolejce; rekurencja.
rozwiazanie zadania 5.7 w zadaniu 4 wynosi:
g*(n,k)=g*(n-2,k-1)+g*(n-1,k)
dla n>=5, k>=2
g*(n,0)=1, g*(n,1)=n
jak to przelozyc dalej aby rozwiazac zadanie 4?
[ Dodano: 22 Marca 2008, 23:43 ]
[ Dodano: 22 Marca 2008, 23:44 ]
g*(n,k)=g*(n-2,k-1)+g*(n-1,k)
dla n>=5, k>=2
g*(n,0)=1, g*(n,1)=n
jak to przelozyc dalej aby rozwiazac zadanie 4?
[ Dodano: 22 Marca 2008, 23:43 ]
zadanie wedlug sprawdzajacego jest uzasadnione dla "i tylko wtedy. Pozostaje wykazac czesc wtedy".*Kasia pisze:Mając wskazówkę, wystarczyło tylko chwilę pomyśleć...
Kostka domina pokrywa dokładnie dwa pola. Czyli k kostek pokrywa dokładnie 2k pól. Ponieważ kwadrat liczby nieparzystej jest liczbą nieparzystą, to jeśli n jest nieparzyste, to liczba pól również jest nieparzysta. Czyli n musi być parzyste.
Zatem n jest parzyste, czyli masz \(\displaystyle{ \frac{1}{2}n^2}\) pól białych i \(\displaystyle{ \frac{1}{2}n^2}\) pól czarnych. Ponieważ kostka pokrywa jedno takie i jedno takie pole, to aby po usunięciu dwóch pól dało się pokryć tablicę, usunięte pola muszą być różnych kolorów.
[ Dodano: 22 Marca 2008, 23:44 ]
ponoc nie wykazano spojnosci grafuUNIX_admin pisze:Ad. 2. to prosciutko:
z def. => graf eulerowski spojny i stopien kazdego wierzcholka parzysty.
2d+1 to liczba nieparzysta
suma stopni wierzcholkow grafu jest 2 razy wieksza od sumy krawedzi (chyba oczywiste)
wiec suma stopni wierzcholkow jest parzysta (2E jest podzielne przez 2)
wuec gdyby d bylo nieparzyste, to d*(2d+1) tez byloby nie parzyste, bo iloczyn licz nieparzystych jest nieparzysty => dostajemy sprzecznosc, a zatem d musi byc parzyste => graf jest eulerowski