Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
2 odpowiedzi w tym temacie

#1 Damian Klimek

Damian Klimek

    Kombinator

  • Użytkownik
  • 174 postów
1
Neutralny
  • Płeć:Mężczyzna

Napisano 25.04.2016 - 17:03

Ile różnych podzbiorów, które nie zawierają dwóch kolejnych liczb całkowitych, posiada zbiór {1, 2, . . . , n}?


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 4210 postów
3410
Profesor
  • Płeć:Mężczyzna

Napisano 26.04.2016 - 07:24

Najpierw określ ile jest podzbiorów co dwa (1,3,5....) ,(2,4,6,...)

Później co trzy (1,4,7,10,...), (2,5,8,11...), (3,6,9,12,...)

co cztery (1,5,9,13,...), (2,6,10,14,...), (3, 7,11,15,...), (4,8,12,16,...)

itd.

 

Albo alternatywnie można podejść do zadania i obliczyć ile jest takich w których przynajmniej raz występują liczny sąsiednie.

 

Trzecie podejście jest bardzo łatwe:

Policz jak to się zachowuje dla kilu początkowych n np. n=3, n=4, n=5, n=6 zauważysz pewną prawidłowość. Następnie trzeba tylko dowieść indukcyjnie

Zauważ, że jeśli zwiększasz n o jeden dostajesz pewną określoną liczbę zbiorów więcej (no jest to uzależniona od aktualnego n, ale jednak zauważalnie).

 

dla n=3 mamy 2 podzbiory (1,3)(3,1)

dla n=4 mamy 6 podzbiorów (1,3)(3,1),(1,4)(4,1),(2,4)(4,2)

dla n=5 mamy 12 podzbiorów (1,3)(3,1),(1,4)(4,1),(2,4)(4,2) (1,5)(5,1)(2,5)(5,2),(3,5)(5,3)(1,3,5)(1,5,3)(3,1,5)(3,5,1)(5,1,3)(5,3,1)

 

rozważ dla dwóch następnych n - co zauważyłeś


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#3 bb314

bb314

    miła suczka

  • $Jr Admin
  • Redaktor
  • 4000 postów
5064
Profesor
  • Płeć:Kobieta

Napisano 27.04.2016 - 09:55

dla n=5 mamy 12 podzbiorów (1,3)(3,1),(1,4)(4,1),(2,4)(4,2) (1,5)(5,1)(2,5)(5,2),(3,5)(5,3)(1,3,5)(1,5,3)(3,1,5)(3,5,1)(5,1,3)(5,3,1)

 

\{1,3\}  i  \{3,1\}  to jest jeden podzbiór

 

 

dla  \bl n=5  mamy \bl12 podzbiorów:

5 jednoelementowych:  \{1\},\ \{2\},\ \{3\},\ \{4\},\ \{5\}

6 dwuelementowych:  \{1,3\},\ \{1,4\},\ \{1,5\},\ \{2,4\},\ \{2,5\},\ \{3,5\}

1 trójelementowy:  \{1,3,5\} 

 

ogólnie - podzbiory mogą być k-elementowe, przy czym  k_{max}=m=\lfloor\frac{n+1}{2}\rfloor

 

wszystkich podzbiorów n-elementowego zbioru, które nie zawierają dwóch kolejnych liczb naturalnych jest  

 

\re\sum_{k=1}^{m}{n+1-k\choose k}

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :shifty: \ :shifty:

Użytkownik bb314 edytował ten post 27.04.2016 - 15:15

  • 2

\ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ Jeśli chcesz powiedzieć \ \ DZIĘKUJĘ \ \ lub \ \ ŁAŁ \ \  to zaloguj się i kliknij znak\ rep_up.png\ nad kreską.\bl\ \ \ \nearrow
..
..
..
..
..
..






Tematy podobne do: Ile?     x