Matematyka dyskretna, zadanie nr 2672
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
geometria post贸w: 865 |  2014-10-05 18:29:42Mamy 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