- LX OM
- LIX OM
- LVIII OM
- LVII OM
- LVI OM
- LV OM
- LIV OM
- LIII OM
- LII OM
- LI OM
- L OM
- XLIX OM
- XLVIII OM
- XLVIII OM - I etap
- XLVIII OM - I - Zadanie 1
- XLVIII OM - I - Zadanie 2
- XLVIII OM - I - Zadanie 3
- XLVIII OM - I - Zadanie 4
- XLVIII OM - I - Zadanie 5
- XLVIII OM - I - Zadanie 6
- XLVIII OM - I - Zadanie 7
- XLVIII OM - I - Zadanie 8
- XLVIII OM - I - Zadanie 9
- XLVIII OM - I - Zadanie 10
- XLVIII OM - I - Zadanie 11
- XLVIII OM - I - Zadanie 12
- XLVIII OM - II etap
- XLVIII OM - III etap
- XLVIII OM - I etap
- XLVII OM
- XLVI OM
- XLV OM
- XLIV OM
- XLIII OM
- XLII OM
- XLI OM
- XL OM
- XXXIX OM
- XXXVIII OM
- XXXVIII OM - I etap
- XXXVIII OM - I - Zadanie 1
- XXXVIII OM - I - Zadanie 2
- XXXVIII OM - I - Zadanie 3
- XXXVIII OM - I - Zadanie 4
- XXXVIII OM - I - Zadanie 5
- XXXVIII OM - I - Zadanie 6
- XXXVIII OM - I - Zadanie 7
- XXXVIII OM - I - Zadanie 8
- XXXVIII OM - I - Zadanie 9
- XXXVIII OM - I - Zadanie 10
- XXXVIII OM - I - Zadanie 11
- XXXVIII OM - I - Zadanie 12
- XXXVIII OM - II etap
- XXXVIII OM - III etap
- XXXVIII OM - I etap
- XXXVII OM
- XXXVII OM - I etap
- XXXVII OM - I - Zadanie 1
- XXXVII OM - I - Zadanie 2
- XXXVII OM - I - Zadanie 3
- XXXVII OM - I - Zadanie 4
- XXXVII OM - I - Zadanie 5
- XXXVII OM - I - Zadanie 6
- XXXVII OM - I - Zadanie 7
- XXXVII OM - I - Zadanie 8
- XXXVII OM - I - Zadanie 9
- XXXVII OM - I - Zadanie 10
- XXXVII OM - I - Zadanie 11
- XXXVII OM - I - Zadanie 12
- XXXVII OM - II etap
- XXXVII OM - III etap
- XXXVII OM - I etap
- XXXVI OM
- XXXV OM
- XXXIV OM
- XXXIII OM
- XXXIII OM - I etap
- XXXIII OM - I - Zadanie 1
- XXXIII OM - I - Zadanie 2
- XXXIII OM - I - Zadanie 3
- XXXIII OM - I - Zadanie 4
- XXXIII OM - I - Zadanie 5
- XXXIII OM - I - Zadanie 6
- XXXIII OM - I - Zadanie 7
- XXXIII OM - I - Zadanie 8
- XXXIII OM - I - Zadanie 9
- XXXIII OM - I - Zadanie 10
- XXXIII OM - I - Zadanie 11
- XXXIII OM - I - Zadanie 12
- XXXIII OM - II etap
- XXXIII OM - III etap
- XXXIII OM - I etap
- XXXII OM
- XXXI OM
- XXX OM
- XXIX OM
- XXVIII OM
- XXVII OM
- XXVI OM
- XXV OM
- XXIV OM
- XXIII OM
- XXII OM
- XXI OM
- XX OM
- XIX OM
- XVIII OM
- XVII OM
- XVI OM
- XV OM
- XIV OM
- XIII OM
- XII OM
- XI OM
- X OM
- IX OM
- VIII OM
- VII OM
- V OM
- VI OM
- IV OM
- III OM
- II OM
- I OM
- Skład komitetów Olimpiady
- Zawody stopnia I (przygotowawcze)
- Zadania z pierwszej olimpiady matematycznej
- I OM - B
- I OM - B - Zadanie 1
- I OM - B - Zadanie 2
- I OM - B - Zadanie 3
- I OM - B - Zadanie 4
- I OM - B - Zadanie 5
- I OM - B - Zadanie 6
- I OM - B - Zadanie 7
- I OM - B - Zadanie 8
- I OM - B - Zadanie 9
- I OM - B - Zadanie 10
- I OM - B - Zadanie 11
- I OM - B - Zadanie 12
- I OM - B - Zadanie 13
- I OM - B - Zadanie 14
- I OM - B - Zadanie 15
- I OM - B - Zadanie 16
- I OM - B - Zadanie 17
- I OM - B - Zadanie 18
- I OM - B - Zadanie 19
- I OM - B - Zadanie 20
- I OM - I etap
- I OM - II etap
- I OM - III etap
- I OM - B
LX OM - I - Zadanie 5
Dla każdej liczby całkowitej wyznaczyć największą
możliwą liczbę różnych podzbiorów zbioru o
następującej własności: Dowolne dwa z tych podzbiorów są rozłączne
lub jeden z nich zawiera się w drugim.
Rozwiązanie
Odpowiedź: podzbiorów.
Oznaczmy szukaną liczbę podzbiorów przez .
Nietrudno spostrzec, że dla następujące
podzbiorów zbioru ma daną w treści zadania własność:
![]() |
Rzeczywiście, dowolny z pierwszych zbiorów ma najwyżej jeden
element, zatem zawiera się w każdym zbiorze, z którym nie jest
rozłączny. Natomiast dla dowolnych dwóch spośród pozostałych
zbiorów ten zbiór, który w powyższym ciągu jest wypisany
wcześniej, zawiera się w drugim zbiorze.
Udowodniliśmy w ten sposób, że
![]() |
Z drugiej strony, niech będą różnymi
podzbiorami zbioru o własności opisanej w treści
zadania. Jeżeli wśród wypisanych podzbiorów nie występuje zbiór
, to możemy go dopisać zwiększając o
liczbę tych
podzbiorów i nie naruszając prawdziwości postulowanego warunku.
Przyjmijmy więc, że .
Spośród zbiorów wybierzmy ten, który
ma najwięcej elementów. Dla ustalenia uwagi niech będzie to
i niech oznacza liczbę jego elementów. Wówczas
.
Ponadto równość oznacza, że
jest zbiorem pustym, co
z uwagi na wybór zbioru jest możliwe jedynie wtedy, gdy
. W dalszej części rozumowania przyjmujemy więc, że
.
Na mocy określenia zbioru każdy ze zbiorów
(
albo jest podzbiorem zbioru
,
albo też jest z nim rozłączny. Dokonując przenumerowania możemy
założyć, iż zbiory są podzbiorami zbioru
, natomiast zbiory
są
rozłączne z .
Zbiory są różnymi podzbiorami
-elementowego zbioru
, z których dowolne dwa albo są
rozłączne, albo jeden zawiera się w drugim. Wynika stąd nierówność
. Wśród
zbiorów
dowolne dwa albo są rozłączne,
albo jeden zawiera się w drugim, przy czym są one podzbiorami
-elementowego zbioru
,
a ponadto nie występuje wśród nich zbiór pusty, jest on bowiem
podzbiorem . Stąd otrzymujemy
i w konsekwencji
![]() |
Skutkiem tego liczba podzbiorów zbioru
o żądanej własności nie przekracza liczby .
Wykazaliśmy zatem, że nie przekracza największej z liczb
![]() |
Jeżeli więc w nierówności (1) równość ma miejsce dla
, to ma ona miejsce również dla
.
Skoro dla nierówność (1) staje się równością, stosując
indukcję stwierdzamy ostatecznie, że dla
.
Komentarze
Dodaj nową odpowiedź