logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 2672

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

geometria
postów: 865
2014-10-05 18:29:42

Mamy do dyspozycji n klatek ustawionych szeregowo, chcemy rozmieścić k nierozróżnialnych lwów tak, by żadne lwy nie sąsiadowały ze sobą. Niech g(n,k) bedzie liczbą sposobów rozmieszczania lwów. Udowodnic ze:
a) g(6, 3)=4
b) g(2k,k)=k+1
c) g(n,k)=g(n-2, k-1)+g(n-1,k), k=2, 3, ...



tumor
postów: 8070
2014-10-05 20:48:27

Zacznijmy radośnie od c), żeby było matematycznie.

Jeśli rozmieszczamy lwy w ilości k na miejscach w ilości n, to układów jest $g(n,k)$, w tym układów, w których lew jest w pierwszej klatce jest $g(n-2,k-1)$ (gdyż taki lew w pierwszej klatce uniemożliwia też obecność lwa w drugiej, zatem pozostałe k-1 lwów umieszczamy w pozostałych n-2 klatkach), natomiast układów, w których lwa nie ma w pierwszej klatce jest $g(n-1,k)$ (gdyż wszystkie k lwów znajduje się w pozostałych n-1 klatkach).



tumor
postów: 8070
2014-10-05 21:11:35

a)

Zacznijmy od zauważenia, że $g(2x-1,x)=1$ dla $x\in N^+$.
Oznacza to, że klatek jest nieparzysta ilość i w każdej z nieparzystym numerem siedzi lew. Inaczej tych x lwów rozmieścić się w $2x-1$ klatkach nie da, więcej lwów się nie da, czyli
$g(2x-1,x+y)=0$ dla $x,y\in N^+$ oraz
$g(2x,x+y)=0$ dla $x,y\in N^+$

Do tego 0 lwów w 0 klatkach rozmieszczamy na 1 sposób, podobnie jednego lwa w jednej klatce oraz 0 lwów w dowolnej ilości klatek.

Wtedy korzystając z c) mamy
$g(6,3)=g(4,2)+g(5,3)=
g(2,1)+g(3,2)+1=g(0,0)+g(1,1)+1+1=4$


---

b) $g(2k,k)=
g(2k-2,k-1)+g(2k-1,k)=g(2k-2,k-1)+1$

Czyli indukcyjnie, $g(0,0)=1$,
jeśli natomiast $g(2k,k)=k+1$, to także $g(2k+2,k+1)=k+2$




geometria
postów: 865
2014-10-06 22:36:51

Dziekuje.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj