Grafy; tablica n na n; n osób w kolejce; rekurencja.

[kswiss]

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.

[*Kasia]

W zadaniu pierwszym skorzystaj z tego, że kostka domina przykrywa dwa pola różnych kolorów.

[kswiss]

moze dodam, ze zupelnie nie rozumiem matematyki dyskretnej i czy moglby ktos poprostu podac rozwiazanie zadania

[*Kasia]

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.

[kinwotar]

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ą.

[UNIX_admin]

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

[kswiss]

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 ]

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.

zadanie wedlug sprawdzajacego jest uzasadnione dla "i tylko wtedy. Pozostaje wykazac czesc wtedy".

[ Dodano: 22 Marca 2008, 23:44 ]

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

ponoc nie wykazano spojnosci grafu