Matematyka dyskretna 1/Ćwiczenia 3: Zliczanie zbiorów i funkcji

From Studia Informatyczne

Zliczanie zbiorów i funkcji

Ćwiczenie 1

Piotrek ma w szufladzie \displaystyle 20 białych skarpetek i \displaystyle 20 czarnych. Lewe skarpetki są zupełnie nieodróżnialne od prawych. Niestety Piotr jest daltonistą i nie potrafi też odróżniać nawet białego i czarnego koloru.

  • Ile skarpetek musi on zabrać, aby mieć pewność, że choć dwie będą tego samego koloru?
  • Ile skarpetek musi on zabrać, aby mieć pewność, że choć \displaystyle 10 będzie tego samego koloru?

Wskazówka

Wykorzystaj Zasadę Szufladkową.

Rozwiązanie

  • Oczywiście dwie skarpetki nie wystarczą, gdyż jedna może być biała a druga czarna. Z Zasady Szufladkowej wzięcie \displaystyle 3 skarpetek daje już pewność powtórzenia jednego z dwu kolorów.
  • Z Uogólnionej Zasady Szufladkowej widzimy, że wybierając \displaystyle 2\cdot9+1=19 skarpetek jeden z kolorów musi być reprezentowany przez przynajmniej \displaystyle 10 skarpet. Znów łatwo zauważyć, że wzięcie mniejszej liczby nie gwarantuje dziesięciu skarpet tego samego koloru.

Ćwiczenie 2

Uzasadnij, że wśród pięciu punktów wybranych wewnątrz kwadratu wielkości \displaystyle 2\times2 zawsze są dwa punkty odległe o nie więcej niż \displaystyle \sqrt{2}.

Wskazówka

Podziel rozważany kwadrat na \displaystyle 4 bloki wielkości \displaystyle 1\times1.

Rozwiązanie

Podzielmy kwadrat \displaystyle 2\times2 na ćwiartki wielkości \displaystyle 1\times1. Zauważmy, że najodleglejszymi od siebie punktami wewnątrz każdej z ćwiartek są naprzeciwległe wierzchołki oddalone o \displaystyle \sqrt{2}. Zasady Szufladkowa gwarantuje jednak, że spośród pięciu punktów przynajmniej dwa znajdą się w tej samej ćwiartce.

Ćwiczenie 3

Pokaż, że z dowolnego \displaystyle 92-elementowego ciągu \displaystyle x_1,\ldots,x_{92} różnych liczb naturalnych można wybrać \displaystyle 7-elementowy podciąg rosnący lub \displaystyle 13-elementowy podciąg malejący.

Wskazówka

Rozważ funkcję przyporządkowującą każdemu elementowi ciągu długość najdłuższego ciągu rosnącego zaczynającego się od niego i długość najdłuższego ciągu malejącego zaczynającego się od niego.

Rozwiązanie

Niech \displaystyle r_i będzie długością najdłuższego ciągu rosnącego zaczynającego się od \displaystyle x_i, a \displaystyle m_i będzie długością najdłuższego ciągu malejącego zaczynającego się od \displaystyle x_i. Zauważmy, że funkcja \displaystyle f: x_i\rightarrow(m_i,r_i) jest injekcją. Rzeczywiście dla \displaystyle i<j jeśli \displaystyle x_i<x_j, to \displaystyle r_i>r_j, jeśli zaś \displaystyle x_i>x_j, to \displaystyle m_i>m_j.

Dla dowodu niewprost załóżmy teraz,

że ciąg \displaystyle x_1,\ldots,x_{92} nie ma ani \displaystyle 7-elementowego ciągu malejącego, ani \displaystyle 13-elementowego ciągu rosnącego. Wtedy injekcja \displaystyle f ma jedynie \displaystyle 7\cdot13=91 możliwych wartości. Zatem \displaystyle f jest injekcją ze zbioru \displaystyle 92-elementowego w \displaystyle 91-elementowy, co oczywiście nie jest możliwe.

Ćwiczenie 4

Piotruś ma \displaystyle 9 klocków białych i \displaystyle 9 klocków czarnych o nieodróżnialnych kształtach. Wołającej go na obiad matce powiedział, że spośród wszystkich możliwych do ułożenia wież o wysokości \displaystyle 10 klocków, ułożył dopiero połowę, a na obiad przyjdzie jak ułoży po kolei wszystkie. Ile różnych wież mu zostało do ułożenia i czy zdąży na obiad?

Wskazówka

Zlicz najpierw wszystkie możliwe do ułożenia wieże o wysokości \displaystyle 10 klocków.

Rozwiązanie

Niech \displaystyle n=100. Przyjmijmy najpierw, że dysponujemy nieograniczoną liczbą białych i czarnych klocków. Wtedy wieża wysokości \displaystyle n jest wyznaczona jednoznacznie poprzez funkcję przypisującą pozycji w wieży (tzn. liczbie \displaystyle 1,\ldots,n) jeden z dwu kolorów. Takich funkcji jest \displaystyle 2^n.

Jednak Piotruś nie może zbudować dwu wież: całej czarnej i całej białej.

Miał więc \displaystyle 2^{10}-2 możliwości, z czego połowa już za nim. Do obiadu pozostało mu więc jeszcze \displaystyle 2^9-1 = 511 wież, więc chyba jego matka straci cierpliwość.

Ćwiczenie 5

Na ile sposobów można rozstawić \displaystyle 8 wież na ponumerowanych polach szachownicy \displaystyle 8\times8 w taki sposób, by żadne dwie nie znajdowały się w polu wzajemnego rażenia?

Wskazówka

Interpretuj każde dopuszczalne rozstawienie wież, jako funkcję ze zbioru wierszy szachownicy w zbiór kolumn.

Rozwiązanie

Rozważamy rozłożenia ośmiu wież, w taki sposób aby w każdej linii i w każdej kolumnie znajdowała się dokładnie jedna wieża. Każde takie rozłożenie jednoznacznie wyznacza bijekcję ze zbioru wierszy \displaystyle \left\lbrace 1,\ldots,8 \right\rbrace w zbiór kolumn \displaystyle \left\lbrace a,\ldots,h \right\rbrace. Jest ich zatem \displaystyle 8!=40320.

Ćwiczenie 6

Ile jest rożnych relacji dwuargumentowych na zbiorze \displaystyle n elementowym? A ile sposród nich jest symetrycznych?

Wskazówka

Relacja na zbiorze \displaystyle A to podzbiór produktu \displaystyle A \times A.

Rozwiązanie

Gdy \displaystyle \left\vert A \right\vert=n, to produkt \displaystyle A \times A ma \displaystyle n^2 elementów i \displaystyle 2^{n^2} podzbiorów.

Po ponumerowaniu elementów zbioru \displaystyle A, relację symetryczną \displaystyle R \subseteq A\times A

wystarczy zadać jedynie na parach \displaystyle (a,b)\in A\times A spełniających \displaystyle a\leq b. Par takich jest:

  • \displaystyle n, dla \displaystyle a=b,
  • \displaystyle \frac{n^2-n}{2}, dla \displaystyle a<b; istotnie par w których \displaystyle a\neq b jest \displaystyle n^2-N, z czego połowa spełnia \displaystyle a<b.

W sumie jest więc \displaystyle n +\frac{n^2-n}{2}= \frac{n(n+1)}{2} par \displaystyle a<b, czyli \displaystyle 2^{\frac{n(n+1)}{2}} relacji symetrycznych.

Ćwiczenie 7

\displaystyle 128-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, gdzie ID są \displaystyle 8-znakowe i, z uwagi na defekt wielu klawiatur, utworzone wyłącznie z liter \displaystyle a,b. Przydzielono je później losowo - na ile sposobów było to możliwe?

Wskazówka

Policz najpierw wszystkie możliwe do utworzenia ID, a potem liczbę możliwych przydziałów tych ID uczestnikom.

Rozwiązanie

Wszystkich możliwych \displaystyle 8-znakowych ID ułożonych z liter \displaystyle a,b, jest tyle co funkcji postaci \displaystyle \mathbb{Z}_8 \longrightarrow \left\lbrace a,b \right\rbrace, czyli \displaystyle 2^8=256. Przydzielenie ich uczetnikom, to injekcja ze zbioru uczestników w zbiór ID. Jest więc \displaystyle \frac{256!}{(256-128)!}=\frac{256!}{128!} takich przydziałów.

Ćwiczenie 8

Ile jest par postaci \displaystyle \left( A,B \right), gdzie \displaystyle A \subseteq B \subseteq X, gdy \displaystyle \left\vert X \right\vert=n?

Wskazówka

Dla pary \displaystyle \left( A,B \right) rozważ funkcję


\displaystyle \chi_{A,B} : X \longrightarrow\left\lbrace 0,1,2 \right\rbrace


zdefiniowaną jako:


\displaystyle \chi_A(x) =  \left\{ \aligned 2,  \quad\mbox{gdy $x\in A$}\\ 1,  \quad\mbox{gdy $x\in B\setminus A$} \\ 0,  \quad\mbox{gdy $x\in X\setminus B$}  \endaligned  \right.


i wywnioskuj, że


\displaystyle \left\vert \left\lbrace \left( A,B \right) : A \subseteq B \subseteq X \right\rbrace \right\vert = 3^{\left\vert X \right\vert}