Matematyka dyskretna, zadanie nr 634
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
natalia1992 postów: 26 | ![]() Ile podzbiorów, które nie zawierają dwóch kolejnych liczb całkowitych, posiada zbiór {1, 2, . . . , n}? |
tumor postów: 8070 | ![]() 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