Przeskocz do treści

Delta mi!

Kącik początkującego olimpijczyka

Zbiory i odwzorowania

Bartłomiej Bzdęga

o artykule ...

  • Publikacja w Delcie: kwiecień 2019
  • Publikacja elektroniczna: 31 marca 2019
  • Wersja do druku [application/pdf]: (390 KB)

Aby wykazać, że zbiory |A i B | mają tyle samo elementów, wystarczy połączyć te elementy w pary (a, b), gdzie a ∈ A i b | ∈B. Jeżeli każdy element zbioru |A i każdy element zbioru B | występuje w nich dokładnie raz, to | A Fakt ten nazywamy zasadą bijekcji.

Bywa, że każdy element zbioru |A sparujemy z innym elementem zbioru |B, ale być może w zbiorze B znajdują się dodatkowo elementy, które nie zostały dobrane w pary. W tej sytuacji | A Jest to dobra metoda szacowania liczby elementów zbioru A, o ile znamy B . Stosujemy ją w zadaniach 5, 8 i 11.

Ciąg binarny to taki, w którym mogą występować tylko zera i jedynki. Na użytek niniejszego artykułu będziemy - ogólniej - nazywać tak każdy ciąg, którego wyrazy mogą przyjmować tylko dwie z góry określone wartości.

Każdy podzbiór |P ⊆{x ,x ,...,x } 1 2 n możemy utożsamić z n-elementowym ciągiem binarnym, w którym na i-tym miejscu stoi |1, gdy xi ∈P; w przeciwnym razie na |i-tym miejscu stoi 0. Z tego wynika, że podzbiorów zbioru |n-elementowego jest tyle, co ciągów binarnych długości |n, czyli |2n. Ponadto ciągów binarnych długości n, zawierających dokładnie k jedynek jest tyle, co k-elementowych podzbiorów zbioru |n-elementowego, czyli  n |(k). Ciągi binarne pomagają rozwiązać zadania 6, 7 i 8.