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

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\cdot 9+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\times 2$ 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\times 1$.

Rozwiązanie

Podzielmy kwadrat $\displaystyle 2\times 2$ na ćwiartki wielkości $\displaystyle 1\times 1$. 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\cdot 13=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\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 $\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\{{\begin{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\end{aligned}}\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 }$