Matematyka dyskretna, zadanie nr 634
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
natalia1992 post贸w: 26 |  2012-11-11 10:09:59Ile podzbior贸w, kt贸re nie zawieraj膮 dw贸ch kolejnych liczb ca艂kowitych, posiada zbi贸r {1, 2, . . . , n}? |
tumor post贸w: 8070 | 2012-11-13 13:14:53 Zbi贸r pusty ma jeden podzbi贸r, kt贸ry spe艂nia warunki zadania, oznaczmy $S_0=1$ Zbi贸r $\{1\}$ ma dwa podzbiory, z tego jeden podzbi贸r zawiera liczb臋 $1$, a drugi nie zawiera. $S_1=2$ Je艣li chcemy doda膰 liczb臋 $2$, to mo偶emy j膮 doda膰 tylko do tych podzbior贸w, kt贸re nie zawieraj膮 liczby $1$. Zatem $S_2=S_1+S_0$ Dla liczby $3$ mamy: $S_3=S_2+S_1$, gdy偶 wszystkie zbiory, kt贸re spe艂nia艂y warunek zadania dla n=2, spe艂niaj膮 te偶 dla n=3, natomiast opr贸cz nich rozwa偶amy jeszcze zbiory spe艂niaj膮ce warunek zadania dla n=1 z do艂膮czon膮 liczb膮 3. Dla kolejnych $n$: $S_{n+2}=S_{n+1}+S_n$ co si臋 nam s艂usznie kojarzy z ci膮giem Fibonacciego, tylko $S_1=2=F_3$. $S_n=F_{n+2}$ |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj