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

Zliczanie zbiorów i funkcji

Ćwiczenie 1

Piotrek ma w szufladzie $20$ białych skarpetek i $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ć $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 $3$ skarpetek daje już pewność powtórzenia jednego z dwu kolorów.
• Z Uogólnionej Zasady Szufladkowej widzimy, że wybierając $2\cdot 9+1=19$ skarpetek jeden z kolorów musi być reprezentowany przez przynajmniej $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 $2\times 2$ zawsze są dwa punkty odległe o nie więcej niż $\sqrt{2}$.

Wskazówka

Podziel rozważany kwadrat na $4$ bloki wielkości $1\times 1$.

Rozwiązanie

Podzielmy kwadrat $2\times 2$ na ćwiartki wielkości $1\times 1$. Zauważmy, że najodleglejszymi od siebie punktami wewnątrz każdej z ćwiartek są naprzeciwległe wierzchołki oddalone o $\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 $92$-elementowego ciągu $x_1,\dots ,x_{92}$ różnych liczb naturalnych można wybrać $7$-elementowy podciąg rosnący lub $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 $r_i$ będzie długością najdłuższego ciągu rosnącego zaczynającego się od $x_i$, a $m_i$ będzie długością najdłuższego ciągu malejącego zaczynającego się od $x_i$. Zauważmy, że funkcja $f:x_i\to (m_i,r_i)$ jest injekcją. Rzeczywiście dla $i<j$ jeśli $x_i<x_j$, to $r_i>r_j$, jeśli zaś $x_i>x_j$, to $m_i>m_j$.

Dla dowodu niewprost załóżmy teraz, że ciąg $x_1,\dots ,x_{92}$ nie ma ani $7$-elementowego ciągu malejącego, ani $13$-elementowego ciągu rosnącego. Wtedy injekcja $f$ ma jedynie $7\cdot 13=91$ możliwych wartości. Zatem $f$ jest injekcją ze zbioru $92$-elementowego w $91$-elementowy, co oczywiście nie jest możliwe.

Ćwiczenie 4

Piotruś ma $9$ klocków białych i $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 $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 $10$ klocków.

Rozwiązanie

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

Jednak Piotruś nie może zbudować dwu wież: całej czarnej i całej białej. Miał więc $2^{10}-2$ możliwości, z czego połowa już za nim. Do obiadu pozostało mu więc jeszcze $2^9-1=511$ wież, więc chyba jego matka straci cierpliwość.

Ćwiczenie 5

Na ile sposobów można rozstawić $8$ wież na ponumerowanych polach szachownicy $8\times 8$ 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 $\{1,\dots ,8\}$ w zbiór kolumn $\{a,\dots ,h\}$. Jest ich zatem $8!=40320$.

Ćwiczenie 6

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

Wskazówka

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

Rozwiązanie

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

Po ponumerowaniu elementów zbioru $A$, relację symetryczną $R\subseteq A\times A$ wystarczy zadać jedynie na parach $(a,b)\in A\times A$ spełniających $a\le b$. Par takich jest:

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

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

Ćwiczenie 7

$128$-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, gdzie ID są $8$-znakowe i, z uwagi na defekt wielu klawiatur, utworzone wyłącznie z liter $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 $8$-znakowych ID ułożonych z liter $a,b$, jest tyle co funkcji postaci ${\mathbb{\mathbb{Z}}}_8⟶\{a,b\}$, czyli $2^8=256$. Przydzielenie ich uczetnikom, to injekcja ze zbioru uczestników w zbiór ID. Jest więc $\frac{256!}{(256-128)!}=\frac{256!}{128!}$ takich przydziałów.

Ćwiczenie 8

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

Wskazówka

Dla pary $(A,B)$ rozważ funkcję

${\chi }_{A,B}:X⟶\{0,1,2\}$

zdefiniowaną jako:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{align}”): {\displaystyle \displaystyle \chi_A(x) = \left\{ \begin{align} 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$} \end{align} \right. }

i wywnioskuj, że

$\left|\{(A,B):A\subseteq B\subseteq X\}\right|=3^{\left|X\right|}$