Matematyka dyskretna, zadanie nr 2219
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
karola1010 post贸w: 46 |  2014-03-12 15:30:55na polce stoi 12 ksiazek. na ile sposob mozna wybrac sposrod nich 5 ksizaek aby wsrod nic nie bylo zadnych dwoch stojacych obok siebie |
tumor post贸w: 8070 | 2014-05-18 10:01:14 Ch艂opskim rozumem rzecz wygl膮da tak: _Ab_Cd_Ef_Gh_I_ Ksi膮偶ki pisane wielkimi literami wybrali艣my, ksi膮偶ek pisanych ma艂ymi literami nie wybrali艣my, natomiast podkre艣lniki oznaczaj膮 miejsca, gdzie by膰 mo偶e znajduj膮 si臋 jeszcze jakie艣 ksi膮偶ki. W sumie mamy 6 podkre艣lnik贸w i 3 ksi膮偶ki, kt贸re mamy tam rozlokowa膰. Na $6$ sposob贸w mo偶emy rzuci膰 3 ksi膮偶ki razem w jeden podkre艣lnik, na $6*5$ sposob贸w mo偶emy w jednym podkre艣lniku mie膰 2 ksi膮偶ki, w innym 1, wreszcie na ${6 \choose 3}$ sposob贸w mo偶emy wybra膰 trzy podkre艣lniki do uzupe艂nienia jedn膮 ksi膮偶k膮. Wynik to $6+6*5+4*5=56$ ---- Gdyby艣my byli sprawnym komputerem, mogliby艣my zagadnienie rozwi膮zywa膰 rekurencyjnie. Nie wymaga to inwencji tw贸rczej. Pierwsza z wybranych przez nas ksi膮偶ek stoi na kt贸rej艣 z pozycji 1-4, bo gdyby sta艂a dalej, mieliby艣my sprzeczno艣膰. a) stoi na pozycji 4, jest 1 mo偶liwo艣膰 rozwi膮zania. b) stoi na pozycji 3. W贸wczas rekurencyjnie wybieramy 4 ksi膮偶ki z 8. c) stoi na pozycji 2, wybieramy 4 ksi膮偶ki z 9 d) stoi na pozycji 1, wybieramy 4 ksi膮偶ki z 10. --- zr贸bmy b) 4z8 Pierwsza z nich jest na pozycji 1 lub 2, 1) na 2, jest 1 rozwi膮zanie 2) na 1, wybieramy 3z6 zr贸bmy c) pierwsza jest na pozycji 1-3 1) na 3, jedno rozwi膮zanie ----- Og贸lnie zatem wybieraj膮c $(k)z(n)$ dostajemy $(k)z(n)=(k-1)z(2k-1)+(k-1)z(2k)+(k-1)z(2k+1)+...+(k-1)z(n-2)$ przy warunkach $(k)z(2k-1)=1$ i $(1)z(n)=n$ ----- No ale mo偶emy te偶 my艣le膰, jak t臋 rekurencj臋 rozbroi膰 i przeanalizowa膰. Wyrazy $1z1, 1z2, 1z3, 1z4,...$ s膮 r贸wne $1,2,3,4,...$ Wyrazy $2z2, 2z3, 2z4,...$ s膮 r贸wne $1,3,6,10,...$ (sumy cz臋艣ciowe ci膮gu wy偶ej) Wyrazy $3z3, 3z4, 3z5,...$ s膮 r贸wne $1,4,10,...$ (sumy cz臋艣ciowe ci膮gu wy偶ej). T臋 w艂asno艣膰 sumowania odnajdujemy w dwumianie Newtona/tr贸jk膮cie Pascala. Dostajemy, 偶e $(k)z(n)={n-k+1 \choose k}$ Co jest bardzo 艂adnym wynikiem. W贸wczas $5z12={8 \choose 5}=56$ |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj