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