Matematyka dyskretna 1/Ćwiczenia 3: Zliczanie zbiorów i funkcji: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Arek (dyskusja | edycje)
Nie podano opisu zmian
Pitab (dyskusja | edycje)
Nie podano opisu zmian
Linia 1: Linia 1:
==Zliczanie zbiorów i funkcji==
==Zliczanie zbiorów i funkcji==


{{cwiczenie|ex zliczanie skarpetki||
{{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|ex zliczanie kwadrat||
{{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|ex zliczanie ciag||
{{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|ex zliczanie wieza||
{{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|ex zliczanie szachy||
{{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|ex zliczanie relacje||
{{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|ex zliczanie ||
{{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 --- na ile sposobów było to możliwe?  
Przydzielono je później losowo - na ile sposobów było to możliwe?  


}}
}}
Linia 177: Linia 160:
</div></div>
</div></div>


{{cwiczenie|ex zliczanie 3 wartosci||
{{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\{
\begin{array} {ll}
\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$}  
\end{array}
\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 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
Rozwiązanie

Ćwiczenie 2

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

Wskazówka
Rozwiązanie

Ćwiczenie 3

Pokaż, że z dowolnego 92-elementowego ciągu x1,,x92 różnych liczb naturalnych można wybrać 7-elementowy podciąg rosnący lub 13-elementowy podciąg malejący.

Wskazówka
Rozwiązanie

Ć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
Rozwiązanie

Ćwiczenie 5

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

Wskazówka
Rozwiązanie

Ćwiczenie 6

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

Wskazówka
Rozwiązanie

Ć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
Rozwiązanie

Ćwiczenie 8

Ile jest par postaci (A,B), gdzie ABX, gdy |X|=n?

Wskazówka