Opublikowane na Archiwum Olimpiady Matematycznej (https://archom.ptm.org.pl)

Strona główna > Wersja do wydruku > Wersja do wydruku

XIII OM - III - Zadanie 4

Zawody matematyczne: 
XIII OM, 1961-1962
Etap: 
III

Iloma sposobami można zbiór $ n $ przedmiotów podzielić na dwa zbiory?

Rozwiązanie

Odpowiedź na postawione pytanie będzie zależała od tego, czy - do rozważanych zbiorów zaliczymy też zbiór pusty, tj. zbiór nie posiadający żadnego elementu (przedmiotu), czy nie; w pierwszym przypadku poszukiwana liczba jest o $ 1 $ większa niż w drugim. Umówimy się rozważać tylko zbiory niepuste.

Niech $ p $ oznacza liczbę wszystkich możliwych podziałów zbioru $ Z $ posiadającego $ n $ elementów, na dwa zbiory, tj. na dwie części.

Wówczas $ 2p $ oznacza liczbę wszystkich możliwych części, czyli podzbiorów zbioru $ Z $, przy czym bierzemy pod uwagę tylko podzbiory właściwe, tj. różne od samego zbioru $ Z $.

Liczbę $ 2p $ wszystkich podzbiorów zbioru o $ n $ elementach znajdziemy, dodając liczby podzbiorów o $ 1, 2, \ldots, (n - 1) $ elementach.

Podzbiorów o $ k $ elementach jest tyle, ile jest kombinacji z $ n $ elementów po $ k $, tj. $ \binom{n}{k} $. Zatem

\[<br /> 2p = \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1}.<br /> \]

Według wzoru dwumianowego Newtona

\[<br /> (2) \qquad (1+1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n}.<br /> \]

Odejmując równości (1) i (2) i uwzględniając, że $ \binom{n}{0} = \binom{n}{n} = 1 $, otrzymujemy

\[<br /> 2^n - 2p = 2<br /> \]

a stąd

\[<br /> p = 2^{n-1} - 1.<br /> \]
© Prawa autorskie Polskie Towarzystwo Matematyczne | Serwis znajduje się na serwerze MIMUW | Projekt: Krystyna Jaworska | Realizacja: Paweł Witkowski INTools, Tomasz Filar
Adres źródła: https://archom.ptm.org.pl/?q=node/1468