Matematyka dyskretna 1/Ćwiczenia 3: Zliczanie zbiorów i funkcji: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
(Nie pokazano 6 wersji utworzonych przez 2 użytkowników) | |||
Linia 1: | Linia 1: | ||
==Zliczanie zbiorów i funkcji== | ==Zliczanie zbiorów i funkcji== | ||
{{cwiczenie| | {{cwiczenie|1|cw 1| | ||
Piotrek ma w szufladzie <math>20</math> białych skarpetek i <math>20</math> czarnych. | |||
Piotrek ma w szufladzie <math> | |||
Lewe skarpetki są zupełnie nieodróżnialne od prawych. | Lewe skarpetki są zupełnie nieodróżnialne od prawych. | ||
Niestety Piotr jest daltonistą i nie potrafi też odróżniać | Niestety Piotr jest daltonistą i nie potrafi też odróżniać | ||
nawet białego i czarnego koloru. | nawet białego i czarnego koloru. | ||
* Ile skarpetek musi on zabrać, aby mieć pewność, | * Ile skarpetek musi on zabrać, aby mieć pewność, że choć dwie będą tego samego koloru? | ||
że choć dwie będą tego samego koloru? | * Ile skarpetek musi on zabrać, aby mieć pewność, że choć <math>10</math> będzie tego samego koloru? | ||
* Ile skarpetek musi on zabrać, aby mieć pewność, | |||
że choć <math> | |||
}} | }} | ||
Linia 19: | Linia 16: | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
* Oczywiście dwie skarpetki nie wystarczą, | * Oczywiście dwie skarpetki nie wystarczą, gdyż jedna może być biała a druga czarna. Z Zasady Szufladkowej wzięcie <math>3</math> skarpetek daje już pewność powtórzenia jednego z dwu kolorów. | ||
gdyż jedna może być biała a druga czarna. | * Z Uogólnionej Zasady Szufladkowej widzimy, że wybierając <math>2\cdot9+1=19</math> skarpetek jeden z kolorów musi być reprezentowany przez przynajmniej <math>10</math> skarpet. Znów łatwo zauważyć, że wzięcie mniejszej liczby nie gwarantuje dziesięciu skarpet tego samego koloru. | ||
Z Zasady Szufladkowej wzięcie <math> | |||
pewność powtórzenia jednego z dwu kolorów. | |||
* Z Uogólnionej Zasady Szufladkowej widzimy, | |||
że wybierając <math> | |||
jeden z kolorów musi być reprezentowany przez przynajmniej <math> | |||
Znów łatwo zauważyć, że wzięcie mniejszej liczby nie gwarantuje dziesięciu skarpet | |||
tego samego koloru. | |||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|2|cw 2| | ||
Uzasadnij, że wśród pięciu punktów wybranych | Uzasadnij, że wśród pięciu punktów wybranych | ||
wewnątrz kwadratu wielkości <math> | wewnątrz kwadratu wielkości <math>2\times2</math> | ||
zawsze są dwa punkty odległe o nie więcej niż <math> | zawsze są dwa punkty odległe o nie więcej niż <math>\sqrt{2}</math>. | ||
}} | }} | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | ||
Podziel rozważany kwadrat na <math> | Podziel rozważany kwadrat na <math>4</math> bloki wielkości <math>1\times1</math>. | ||
</div></div> | </div></div> | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
Podzielmy kwadrat <math> | Podzielmy kwadrat <math>2\times2</math> na ćwiartki wielkości <math>1\times1</math>. | ||
Zauważmy, że najodleglejszymi od siebie punktami wewnątrz każdej z ćwiartek | Zauważmy, że najodleglejszymi od siebie punktami wewnątrz każdej z ćwiartek | ||
są naprzeciwległe wierzchołki oddalone o <math> | są naprzeciwległe wierzchołki oddalone o <math>\sqrt{2}</math>. | ||
Zasady Szufladkowa gwarantuje jednak, że spośród pięciu punktów przynajmniej dwa | Zasady Szufladkowa gwarantuje jednak, że spośród pięciu punktów przynajmniej dwa | ||
znajdą się w tej samej ćwiartce. | znajdą się w tej samej ćwiartce. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|3|cw 3| | ||
Pokaż, że z dowolnego <math>92</math>-elementowego ciągu <math>x_1,\ldots,x_{92}</math> | |||
Pokaż, że z dowolnego <math> | |||
różnych liczb naturalnych | różnych liczb naturalnych | ||
można wybrać <math> | można wybrać <math>7</math>-elementowy podciąg rosnący lub <math>13</math>-elementowy podciąg malejący. | ||
}} | }} | ||
Linia 66: | Linia 54: | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
Niech <math> | Niech <math>r_i</math> będzie długością najdłuższego ciągu rosnącego | ||
zaczynającego się od <math> | zaczynającego się od <math>x_i</math>, | ||
a <math> | a <math>m_i</math> będzie długością najdłuższego ciągu malejącego | ||
zaczynającego się od <math> | zaczynającego się od <math>x_i</math>. | ||
Zauważmy, że funkcja <math> | Zauważmy, że funkcja <math>f: x_i\rightarrow(m_i,r_i)</math> jest injekcją. | ||
Rzeczywiście dla <math> | Rzeczywiście dla <math>i<j</math> jeśli <math>x_i<x_j</math>, to <math>r_i>r_j</math>, jeśli zaś <math>x_i>x_j</math>, to <math>m_i>m_j</math>. | ||
Dla dowodu niewprost załóżmy teraz, | Dla dowodu niewprost załóżmy teraz, | ||
że ciąg <math> | że ciąg <math>x_1,\ldots,x_{92}</math> nie ma ani <math>7</math>-elementowego ciągu malejącego, | ||
ani <math> | ani <math>13</math>-elementowego ciągu rosnącego. | ||
Wtedy injekcja <math> | Wtedy injekcja <math>f</math> ma jedynie <math>7\cdot13=91</math> możliwych wartości. | ||
Zatem <math> | Zatem <math>f</math> jest injekcją ze zbioru <math>92</math>-elementowego w <math>91</math>-elementowy, | ||
co oczywiście nie jest możliwe. | co oczywiście nie jest możliwe. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|4|cw 4| | ||
Piotruś ma <math>9</math> klocków białych i <math>9</math> klocków czarnych | |||
Piotruś ma <math> | |||
o nieodróżnialnych kształtach. | o nieodróżnialnych kształtach. | ||
Wołającej go na obiad matce powiedział, że spośród | Wołającej go na obiad matce powiedział, że spośród | ||
wszystkich możliwych do ułożenia wież o wysokości <math> | wszystkich możliwych do ułożenia wież o wysokości <math>10</math> klocków, | ||
ułożył dopiero połowę, a na obiad przyjdzie jak ułoży po kolei wszystkie. | 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? | Ile różnych wież mu zostało do ułożenia i czy zdąży na obiad? | ||
Linia 93: | Linia 80: | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | ||
Zlicz najpierw wszystkie możliwe do ułożenia wieże o wysokości <math> | Zlicz najpierw wszystkie możliwe do ułożenia wieże o wysokości <math>10</math> klocków. | ||
</div></div> | </div></div> | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
Niech <math> | Niech <math>n=100</math>. | ||
Przyjmijmy najpierw, że dysponujemy nieograniczoną liczbą białych i czarnych klocków. | Przyjmijmy najpierw, że dysponujemy nieograniczoną liczbą białych i czarnych klocków. | ||
Wtedy wieża wysokości <math> | Wtedy wieża wysokości <math>n</math> jest wyznaczona jednoznacznie | ||
poprzez funkcję przypisującą pozycji w wieży | poprzez funkcję przypisującą pozycji w wieży | ||
(tzn. liczbie <math> | (tzn. liczbie <math>1,\ldots,n</math>) jeden z dwu kolorów. | ||
Takich funkcji jest <math> | Takich funkcji jest <math>2^n</math>. | ||
Jednak Piotruś nie może zbudować dwu wież: całej czarnej i całej białej. | Jednak Piotruś nie może zbudować dwu wież: całej czarnej i całej białej. | ||
Miał więc <math> | Miał więc <math>2^{10}-2</math> możliwości, z czego połowa już za nim. | ||
Do obiadu pozostało mu więc jeszcze <math> | Do obiadu pozostało mu więc jeszcze <math>2^9-1 = 511</math> wież, | ||
więc chyba jego matka straci cierpliwość. | więc chyba jego matka straci cierpliwość. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|5|cw 5| | ||
Na ile sposobów można rozstawić <math>8</math> wież na ponumerowanych polach | |||
Na ile sposobów można rozstawić <math> | szachownicy <math>8\times8</math> w taki sposób, | ||
szachownicy <math> | |||
by żadne dwie nie znajdowały się w polu wzajemnego rażenia? | by żadne dwie nie znajdowały się w polu wzajemnego rażenia? | ||
Linia 127: | Linia 113: | ||
w taki sposób aby w każdej linii i w każdej kolumnie znajdowała się dokładnie jedna wieża. | 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ę | Każde takie rozłożenie jednoznacznie wyznacza bijekcję | ||
ze zbioru wierszy <math> | ze zbioru wierszy <math>\left\lbrace 1,\ldots,8 \right\rbrace</math> w zbiór kolumn <math>\left\lbrace a,\ldots,h \right\rbrace</math>. | ||
Jest ich zatem <math> | Jest ich zatem <math>8!=40320</math>. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|6|cw 6| | ||
Ile jest rożnych relacji dwuargumentowych na zbiorze <math>n</math> elementowym? | |||
Ile jest rożnych relacji dwuargumentowych na zbiorze <math> | |||
A ile sposród nich jest symetrycznych? | A ile sposród nich jest symetrycznych? | ||
Linia 139: | Linia 124: | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | ||
Relacja na zbiorze <math> | Relacja na zbiorze <math>A</math> to podzbiór produktu <math>A \times A</math>. | ||
</div></div> | </div></div> | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
Gdy <math> | Gdy <math>\left\vert A \right\vert=n</math>, to produkt <math>A \times A</math> ma <math>n^2</math> elementów i <math>2^{n^2}</math> podzbiorów. | ||
Po ponumerowaniu elementów zbioru <math> | Po ponumerowaniu elementów zbioru <math>A</math>, relację symetryczną <math>R \subseteq A\times A</math> | ||
wystarczy zadać jedynie na parach <math> | wystarczy zadać jedynie na parach <math>(a,b)\in A\times A</math> spełniających <math>a\leq b</math>. | ||
Par takich jest: | Par takich jest: | ||
* <math> | * <math>n</math>, dla <math>a=b</math>, | ||
* <math> | * <math>\frac{n^2-n}{2}</math>, dla <math>a<b</math>; istotnie par w których <math>a\neq b</math> jest <math>n^2-N</math>, z czego połowa spełnia <math>a<b</math>. | ||
z czego połowa spełnia <math> | |||
W sumie jest więc <math> | W sumie jest więc <math>n +\frac{n^2-n}{2}= \frac{n(n+1)}{2}</math> par <math>a<b</math>, czyli | ||
<math> | <math>2^{\frac{n(n+1)}{2}}</math> relacji symetrycznych. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|7|cw 7| | ||
<math>128</math>-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, | |||
<math> | gdzie ID są <math>8</math>-znakowe i, z uwagi na defekt wielu klawiatur, | ||
gdzie ID są <math> | utworzone wyłącznie z liter <math>a,b</math>. | ||
utworzone wyłącznie z liter <math> | Przydzielono je później losowo - na ile sposobów było to możliwe? | ||
Przydzielono je później losowo | |||
}} | }} | ||
Linia 171: | Linia 154: | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | ||
Wszystkich możliwych <math> | Wszystkich możliwych <math>8</math>-znakowych ID ułożonych z liter <math>a,b</math>, jest tyle co | ||
funkcji postaci <math> | funkcji postaci <math>\mathbb{Z}_8 \longrightarrow \left\lbrace a,b \right\rbrace</math>, czyli <math>2^8=256</math>. | ||
Przydzielenie ich uczetnikom, to injekcja ze zbioru uczestników w zbiór ID. | Przydzielenie ich uczetnikom, to injekcja ze zbioru uczestników w zbiór ID. | ||
Jest więc <math> | Jest więc <math>\frac{256!}{(256-128)!}=\frac{256!}{128!}</math> takich przydziałów. | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|8|cw 8| | ||
Ile jest par postaci <math>\left( A,B \right)</math>, gdzie <math>A \subseteq B \subseteq X</math>, gdy <math>\left\vert X \right\vert=n</math>? | |||
Ile jest par postaci <math> | |||
}} | }} | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | ||
Dla pary <math> | Dla pary <math>\left( A,B \right)</math> rozważ funkcję | ||
<center><math> | |||
<center><math>\chi_{A,B} : X \longrightarrow\left\lbrace 0,1,2 \right\rbrace | |||
</math></center> | </math></center> | ||
zdefiniowaną jako: | zdefiniowaną jako: | ||
<center><math> | |||
<center><math>\chi_A(x) = | |||
\left\{ | \left\{ | ||
\begin{ | \begin{align} | ||
2, | 2, \quad\mbox{gdy } x\in A \\ | ||
1, | 1, \quad\mbox{gdy } x\in B \setminus A \\ | ||
0, | 0, \quad\mbox{gdy } x\in X \setminus B | ||
\end{ | \end{align} | ||
\right. | \right.</math></center> | ||
</math></center> | |||
i wywnioskuj, że | i wywnioskuj, że | ||
<center><math> | |||
<center><math>\left\vert \left\lbrace \left( A,B \right) : A \subseteq B \subseteq X \right\rbrace \right\vert = 3^{\left\vert X \right\vert} | |||
</math></center> | </math></center> | ||
</div></div> | </div></div> |
Aktualna wersja na dzień 07:21, 12 wrz 2023
Zliczanie zbiorów i funkcji
Ćwiczenie 1
Piotrek ma w szufladzie białych skarpetek i 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ć będzie tego samego koloru?
Ćwiczenie 2
Uzasadnij, że wśród pięciu punktów wybranych wewnątrz kwadratu wielkości zawsze są dwa punkty odległe o nie więcej niż .
Ćwiczenie 3
Pokaż, że z dowolnego -elementowego ciągu różnych liczb naturalnych można wybrać -elementowy podciąg rosnący lub -elementowy podciąg malejący.
Ćwiczenie 4
Piotruś ma klocków białych i 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 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?
Ćwiczenie 5
Na ile sposobów można rozstawić wież na ponumerowanych polach szachownicy w taki sposób, by żadne dwie nie znajdowały się w polu wzajemnego rażenia?
Ćwiczenie 6
Ile jest rożnych relacji dwuargumentowych na zbiorze elementowym? A ile sposród nich jest symetrycznych?
Ćwiczenie 7
-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, gdzie ID są -znakowe i, z uwagi na defekt wielu klawiatur, utworzone wyłącznie z liter . Przydzielono je później losowo - na ile sposobów było to możliwe?
Ćwiczenie 8
Ile jest par postaci , gdzie , gdy ?