Matematyka dyskretna 1/Ćwiczenia 3: Zliczanie zbiorów i funkcji: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
Linia 1: | Linia 1: | ||
==Zliczanie zbiorów i funkcji== | ==Zliczanie zbiorów i funkcji== | ||
{{cwiczenie| | {{cwiczenie|1|cw 1| | ||
Piotrek ma w szufladzie <math>\displaystyle 20</math> białych skarpetek i <math>\displaystyle 20</math> czarnych. | Piotrek ma w szufladzie <math>\displaystyle 20</math> białych skarpetek i <math>\displaystyle 20</math> czarnych. | ||
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>\displaystyle 10</math> będzie tego samego koloru? | ||
* Ile skarpetek musi on zabrać, aby mieć pewność, | |||
że choć <math>\displaystyle 10</math> będzie tego samego koloru? | |||
}} | }} | ||
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>\displaystyle 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>\displaystyle 2\cdot9+1=19</math> skarpetek jeden z kolorów musi być reprezentowany przez przynajmniej <math>\displaystyle 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>\displaystyle 3</math> skarpetek daje już | |||
pewność powtórzenia jednego z dwu kolorów. | |||
* Z Uogólnionej Zasady Szufladkowej widzimy, | |||
że wybierając <math>\displaystyle 2\cdot9+1=19</math> skarpetek | |||
jeden z kolorów musi być reprezentowany przez przynajmniej <math>\displaystyle 10</math> skarpet. | |||
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>\displaystyle 2\times2</math> | wewnątrz kwadratu wielkości <math>\displaystyle 2\times2</math> | ||
Linia 51: | Linia 40: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|3|cw 3| | ||
Pokaż, że z dowolnego <math>\displaystyle 92</math>-elementowego ciągu <math>\displaystyle x_1,\ldots,x_{92}</math> | Pokaż, że z dowolnego <math>\displaystyle 92</math>-elementowego ciągu <math>\displaystyle x_1,\ldots,x_{92}</math> | ||
różnych liczb naturalnych | różnych liczb naturalnych | ||
Linia 81: | Linia 69: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|4|cw 4| | ||
Piotruś ma <math>\displaystyle 9</math> klocków białych i <math>\displaystyle 9</math> klocków czarnych | Piotruś ma <math>\displaystyle 9</math> klocków białych i <math>\displaystyle 9</math> klocków czarnych | ||
o nieodróżnialnych kształtach. | o nieodróżnialnych kształtach. | ||
Linia 110: | Linia 97: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|5|cw 5| | ||
Na ile sposobów można rozstawić <math>\displaystyle 8</math> wież na ponumerowanych polach | Na ile sposobów można rozstawić <math>\displaystyle 8</math> wież na ponumerowanych polach | ||
szachownicy <math>\displaystyle 8\times8</math> w taki sposób, | szachownicy <math>\displaystyle 8\times8</math> w taki sposób, | ||
Linia 131: | Linia 117: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|6|cw 6| | ||
Ile jest rożnych relacji dwuargumentowych na zbiorze <math>\displaystyle n</math> elementowym? | Ile jest rożnych relacji dwuargumentowych na zbiorze <math>\displaystyle n</math> elementowym? | ||
A ile sposród nich jest symetrycznych? | A ile sposród nich jest symetrycznych? | ||
Linia 149: | Linia 134: | ||
Par takich jest: | Par takich jest: | ||
* <math>\displaystyle n</math>, dla <math>\displaystyle a=b</math>, | * <math>\displaystyle n</math>, dla <math>\displaystyle a=b</math>, | ||
* <math>\displaystyle \frac{n^2-n}{2}</math>, dla <math>\displaystyle a<b</math>; istotnie par w których <math>\displaystyle a\neq b</math> jest <math>\displaystyle n^2-N</math>, | * <math>\displaystyle \frac{n^2-n}{2}</math>, dla <math>\displaystyle a<b</math>; istotnie par w których <math>\displaystyle a\neq b</math> jest <math>\displaystyle n^2-N</math>, z czego połowa spełnia <math>\displaystyle a<b</math>. | ||
z czego połowa spełnia <math>\displaystyle a<b</math>. | |||
W sumie jest więc <math>\displaystyle n +\frac{n^2-n}{2}= \frac{n(n+1)}{2}</math> par <math>\displaystyle a<b</math>, czyli | W sumie jest więc <math>\displaystyle n +\frac{n^2-n}{2}= \frac{n(n+1)}{2}</math> par <math>\displaystyle a<b</math>, czyli | ||
Linia 156: | Linia 140: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|7|cw 7| | ||
<math>\displaystyle 128</math>-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, | <math>\displaystyle 128</math>-miu uczestnikom pewnej konferencji informatycznej przygotowano konta komputerowe, | ||
gdzie ID są <math>\displaystyle 8</math>-znakowe i, z uwagi na defekt wielu klawiatur, | gdzie ID są <math>\displaystyle 8</math>-znakowe i, z uwagi na defekt wielu klawiatur, | ||
utworzone wyłącznie z liter <math>\displaystyle a,b</math>. | utworzone wyłącznie z liter <math>\displaystyle a,b</math>. | ||
Przydzielono je później losowo | Przydzielono je później losowo - na ile sposobów było to możliwe? | ||
}} | }} | ||
Linia 177: | Linia 160: | ||
</div></div> | </div></div> | ||
{{cwiczenie| | {{cwiczenie|8|cw 8| | ||
Ile jest par postaci <math>\displaystyle \left( A,B \right)</math>, gdzie <math>\displaystyle A \subseteq B \subseteq X</math>, gdy <math>\displaystyle \left\vert X \right\vert=n</math>? | Ile jest par postaci <math>\displaystyle \left( A,B \right)</math>, gdzie <math>\displaystyle A \subseteq B \subseteq X</math>, gdy <math>\displaystyle \left\vert X \right\vert=n</math>? | ||
Linia 185: | Linia 167: | ||
<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>\displaystyle \left( A,B \right)</math> rozważ funkcję | Dla pary <math>\displaystyle \left( A,B \right)</math> rozważ funkcję | ||
<center><math>\displaystyle \chi_{A,B} : X \longrightarrow\left\lbrace 0,1,2 \right\rbrace | <center><math>\displaystyle \chi_{A,B} : X \longrightarrow\left\lbrace 0,1,2 \right\rbrace | ||
</math></center> | </math></center> | ||
zdefiniowaną jako: | zdefiniowaną jako: | ||
<center><math>\displaystyle \chi_A(x) = | <center><math>\displaystyle \chi_A(x) = | ||
\left\{ | \left\{ | ||
\ | \aligned | ||
2, &\mbox{gdy $x\in A$}\\ | 2, &\mbox{gdy $x\in A$}\\ | ||
1, &\mbox{gdy $x\in B\setminus A$} \\ | 1, &\mbox{gdy $x\in B\setminus A$} \\ | ||
0, &\mbox{gdy $x\in X\setminus B$} | 0, &\mbox{gdy $x\in X\setminus B$} | ||
\ | \endaligned | ||
\right. | \right. | ||
</math></center> | </math></center> | ||
i wywnioskuj, że | i wywnioskuj, że | ||
<center><math>\displaystyle \left\vert \left\lbrace \left( A,B \right) : A \subseteq B \subseteq X \right\rbrace \right\vert = 3^{\left\vert X \right\vert} | <center><math>\displaystyle \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> |
Wersja z 08:53, 2 wrz 2006
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 ?