Matematyka dyskretna, zadanie nr 2672
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / 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