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
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|ex zliczanie skarpetki||
{{cwiczenie|1|cw 1|
 
Piotrek ma w szufladzie <math>20</math>  białych skarpetek i <math>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>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>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>\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>2\times2</math>  
zawsze są dwa punkty odległe o nie więcej niż <math>\displaystyle \sqrt{2}</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>\displaystyle 4</math> bloki wielkości <math>\displaystyle 1\times1</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>\displaystyle 2\times2</math> na ćwiartki wielkości <math>\displaystyle 1\times1</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>\displaystyle \sqrt{2}</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|ex zliczanie ciag||
{{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>\displaystyle 92</math>-elementowego ciągu <math>\displaystyle x_1,\ldots,x_{92}</math>  
różnych liczb naturalnych  
różnych liczb naturalnych  
można wybrać <math>\displaystyle 7</math>-elementowy podciąg rosnący lub <math>\displaystyle 13</math>-elementowy podciąg malejący.
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>\displaystyle r_i</math> będzie długością najdłuższego ciągu rosnącego  
Niech <math>r_i</math> będzie długością najdłuższego ciągu rosnącego  
zaczynającego się od <math>\displaystyle x_i</math>,  
zaczynającego się od <math>x_i</math>,  
a <math>\displaystyle m_i</math> będzie długością najdłuższego ciągu malejącego  
a <math>m_i</math> będzie długością najdłuższego ciągu malejącego  
zaczynającego się od <math>\displaystyle x_i</math>.  
zaczynającego się od <math>x_i</math>.  
Zauważmy, że funkcja <math>\displaystyle f: x_i\rightarrow(m_i,r_i)</math> jest injekcją.  
Zauważmy, że funkcja <math>f: x_i\rightarrow(m_i,r_i)</math> jest injekcją.  
Rzeczywiście dla <math>\displaystyle i<j</math> jeśli <math>\displaystyle x_i<x_j</math>, to <math>\displaystyle r_i>r_j</math>, jeśli zaś <math>\displaystyle x_i>x_j</math>, to <math>\displaystyle m_i>m_j</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>\displaystyle x_1,\ldots,x_{92}</math> nie ma ani <math>\displaystyle 7</math>-elementowego ciągu malejącego,
że ciąg <math>x_1,\ldots,x_{92}</math> nie ma ani <math>7</math>-elementowego ciągu malejącego,
ani  <math>\displaystyle 13</math>-elementowego ciągu rosnącego.  
ani  <math>13</math>-elementowego ciągu rosnącego.  
Wtedy injekcja <math>\displaystyle f</math>  ma jedynie <math>\displaystyle 7\cdot13=91</math> możliwych wartości.  
Wtedy injekcja <math>f</math>  ma jedynie <math>7\cdot13=91</math> możliwych wartości.  
Zatem <math>\displaystyle f</math> jest injekcją ze zbioru <math>\displaystyle 92</math>-elementowego w <math>\displaystyle 91</math>-elementowy,  
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|ex zliczanie wieza||
{{cwiczenie|4|cw 4|
 
Piotruś ma  <math>9</math> klocków białych i <math>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.
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>\displaystyle 10</math> klocków,  
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>\displaystyle 10</math> klocków.
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>\displaystyle n=100</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>\displaystyle n</math> jest wyznaczona jednoznacznie  
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>\displaystyle 1,\ldots,n</math>) jeden z dwu kolorów.
(tzn. liczbie  <math>1,\ldots,n</math>) jeden z dwu kolorów.
Takich funkcji jest <math>\displaystyle 2^n</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>\displaystyle 2^{10}-2</math> możliwości, z czego połowa już za nim.
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>\displaystyle 2^9-1 = 511</math> wież,  
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|ex zliczanie szachy||
{{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>\displaystyle 8</math> wież na ponumerowanych polach  
szachownicy <math>8\times8</math> w taki sposób,  
szachownicy <math>\displaystyle 8\times8</math> w taki sposób,  
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>\displaystyle \left\lbrace 1,\ldots,8 \right\rbrace</math> w zbiór kolumn <math>\displaystyle \left\lbrace a,\ldots,h \right\rbrace</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>\displaystyle 8!=40320</math>.
Jest ich zatem <math>8!=40320</math>.
</div></div>
</div></div>


{{cwiczenie|ex zliczanie relacje||
{{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>\displaystyle n</math> elementowym?
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>\displaystyle A</math> to podzbiór produktu <math>\displaystyle A \times A</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>\displaystyle \left\vert A \right\vert=n</math>, to produkt <math>\displaystyle A \times A</math> ma <math>\displaystyle n^2</math> elementów i <math>\displaystyle 2^{n^2}</math> podzbiorów.
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>\displaystyle A</math>, relację symetryczną <math>\displaystyle R \subseteq A\times A</math>  
Po ponumerowaniu elementów zbioru <math>A</math>, relację symetryczną <math>R \subseteq A\times A</math>  
wystarczy zadać jedynie na parach <math>\displaystyle (a,b)\in A\times A</math> spełniających <math>\displaystyle a\leq b</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>\displaystyle n</math>, dla <math>\displaystyle a=b</math>,
* <math>n</math>, dla <math>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>\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>\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>n +\frac{n^2-n}{2}= \frac{n(n+1)}{2}</math> par <math>a<b</math>, czyli
<math>\displaystyle 2^{\frac{n(n+1)}{2}}</math> relacji symetrycznych.
<math>2^{\frac{n(n+1)}{2}}</math> relacji symetrycznych.
</div></div>
</div></div>


{{cwiczenie|ex zliczanie ||
{{cwiczenie|7|cw 7|
 
<math>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>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>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 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>\displaystyle 8</math>-znakowych ID ułożonych z liter <math>\displaystyle a,b</math>, jest tyle co  
Wszystkich możliwych <math>8</math>-znakowych ID ułożonych z liter <math>a,b</math>, jest tyle co  
funkcji postaci <math>\displaystyle \mathbb{Z}_8 \longrightarrow \left\lbrace a,b \right\rbrace</math>, czyli <math>\displaystyle 2^8=256</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>\displaystyle \frac{256!}{(256-128)!}=\frac{256!}{128!}</math> takich przydziałów.  
Jest więc <math>\frac{256!}{(256-128)!}=\frac{256!}{128!}</math> takich przydziałów.  
</div></div>
</div></div>


{{cwiczenie|ex zliczanie 3 wartosci||
{{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>\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>?


}}
}}


<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>\left( A,B \right)</math> rozważ funkcję


<center><math>\displaystyle \chi_{A,B} : X \longrightarrow\left\lbrace 0,1,2 \right\rbrace
 
<center><math>\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>\chi_A(x) =  
\left\{
\left\{
\begin{array} {ll}
\begin{align}
2,  &\mbox{gdy $x\in A$}\\
2,  \quad\mbox{gdy } x\in A \\
1,  &\mbox{gdy $x\in B\setminus A$} \\
1,  \quad\mbox{gdy } x\in B \setminus A \\
0,  &\mbox{gdy $x\in X\setminus B$}
0,  \quad\mbox{gdy } x\in X \setminus B  
\end{array}  
\end{align}  
\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>\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 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