Zpět na stránku cvika

2. cvičení

Dnes se podíváme na důkazy sporem a jejich speciální případ, důkaz metodou nejmenšího protipříkladu. Potom se zběžně podíváme na relace.

Důkazy sporem

Příklad 1. Dokažte, že prvočísel je nekonečně mnoho.

Zobraz nápovědu Skryj nápovědu

Kdyby bylo prvočísel konečně mnoho, mohli bychom je všechny posčítat. Nebo s nimi udělat i něco zajímavějšího. Nezapomeňte také, že $k\cdot a+b$ je dělitelné $a$, právě když je $b$ dělitelné $a$.

Příklad 2. Kolem kulatého stolu sedí 22 dětí, 11 kluků a 11 holek. Dokažte, že alespoň jedno dítě (ne nutně kluk) má po obou svých stranách holky.

Důkazy metodou nejmenšího protipříkladu

Příklad 3. Dokažte, že $\sqrt 2$ je iracionální číslo. Dokážete dokázat obecnější verzi, která říká, že každá (přirozená) odmocnina (přirozeného) čísla je buď přirozená, nebo iracionální?

Zobraz nápovědu Skryj nápovědu

Definice racionálního čísla zní, že $a$ je racionální, právě když existuje číslo $p\in \mathbb N_0$ a celé číslo $q\in \mathbb Z\setminus\{0\}$ takové, že $\frac pq = a$.


Zobraz řešení Skryj řešení

Nechť $p$ a $q$ zmíněná v nápovědě pro spor existují. Navíc budiž $p$ nejmenší takové, že pro něj existuje $q$ s danými vlastnostmi. Potom zřejmě $\frac {p^2}{q^2}=2$. Pak ale musí platit alespoň jedna z následujících možností:

  1. $p$ není dělitelné dvěma. Pak $\frac {p^2}{q^2}$ zjevně taky ne, což je ale spor s tvrzením, že tato hodnota je dva.
  2. $p$ je dělitelné dvěma a $q$ ne. Pak je $\frac {p^2}{q^2}$ zjevně dělitelné čtyřmi, což je opět spor s tvrzením, že je tato hodnota dva.
  3. $p$ je dělitelné dvěma a $q$ taky. Pak ale zřejmě $p/2$ i $q/2$ jsou celá čísla a protože $\frac {p^2}{q^2}=2$, tak i $\frac{(p/2)^2}{(q/2)^2}=2$, což je ve sporu s tím, že $p$ je nejmenší přirozené číslo, pro něž existuje $q$ takové, že $\frac pq = \sqrt 2$, protože $p/2$ má tuto vlastnost taky.
To znamená, že taková čísla $p$ a $q$ nemohou existovat.

Příklad 4. Nalezněte všechna řešení následující rovnice $$a^2 + b^2= 3(c^2+d^2)$$ taková, že $a$, $b$, $c$ i $d$ jsou celá čísla.


Příklad 5. (dvojhvězdičkový) Mějme přirozená čísla $x$, $y$ a $z$ po dvou nesoudělná taková, že $x^2+y^2=z^2$. Pak tato čísla nazveme primitivní Pythagorejskou trojicí. Pro takové trojice platí, že existují přirozená čísla $p$ a $q$ taková, že $x=2pq$, $y=p^2-q^2$ a $z=p^2 + q^2$, kde $p$ a $q$ jsou nesoudělná čísla, z nichž je navíc právě jedno sudé. Dokažte s využitím tohoto tvrzení, že neexistují žádná přirozená čísla $a$, $b$, $c$ taková, že $a^4 + b^4 = c^4$.

Příklad 6. Lesník si vysázel nekonečnou lesní školku, a to tak, že v rovině vysadil strom do každého bodu s celočíselnými souřadnicemi. Tuto školku nechal několik let růst. Při následné procházce zjistil, že jeho školka je skutečně obdivuhodná – nejen, že má každý strom v centimetrech celočíselnou výšku, ale navíc je každý strom stejně vysoký, jako průměr jeho čtyř sousedů. Dokažte, že ve zmíněné lesní školce jsou všechny stromy stejně vysoké (Jedná se o normální stromy, jejich výšky nemůžou být záporné).

Příklad 7. František si nakreslil do sešitu několik modrých bodů a několik červených bodů, přičemž žádné dva nakreslené body nesplývají. Pak si všiml, že na úsečce spojující libovolné dva různé modré je alespoň jeden červený, a naopak na úsečce spojující libovolné dva různé červené je alespoň jeden modrý. Ukažte, že je bodů buď nekonečně mnoho, nebo leží všechny na jedné přímce.

Zobraz nápovědu Skryj nápovědu

Podívejte se na obsahy trojúhelníků s vrcholy v těchto bodech.

Příklad 8. (dvojhvězdičkový) Mějme množinu bodů v rovině takovou, že žádné 3 neleží na jedné přímce. Dokažte, že tvoří-li nějakých 6 z nich konvexní šestiúhelník, pak nutně nějakých 5 z nich tvoří konvexní pětiúhelník, v němž již neleží žádné další vybrané body.

Zobraz nápovědu Skryj nápovědu

Hledejte šestiúhelník, v němž leží nejméně dalších vybraných bodů.

Relace


Příklad 9. Na konečné množině najděte relaci, která je symetrická i antisymetrická, a relaci, která není ani symetrická ani antisymetrická.

Příklad 10. Nechť $X$ je konečná množina a $R$ a $S$ nechť jsou relace na této množině. Rozhodněte, zda platí tvrzení: "Má-li $R$ i $S$ vlastnost $V$, pak i $R \oplus S$ má vlastnost $V$" pro $V \in \{\text{reflexivní, tranzitivní,}$ $\text{symetrická}\}$ a $\oplus \in \{\cap,\cup,\setminus,\operatorname{\triangle},\circ,^{-1}\}$.

$R\cap S$ $R \cup S$ $R \setminus S$ $R \operatorname{\triangle} S$ $R\circ S$ $R^{-1}$
reflexivní
symetrická
antisymetrická
tranzitivní

Příklad 11. Rozhodněte, zda jsou následující relace na množině $X$ ekvivalence. Pokud ano, popište třídy ekvivalence.

O číslu $a\in \mathbb Z\setminus\{0\}$ řekneme, že dělí $b \in \mathbb Z$, právě pokud $b/a \in \mathbb Z$. "$a$ dělí $b$" můžeme také zapsat jako "$a\mid b$".
  1. $X = \mathbb N$, $p$ je dané přirozené číslo, $(a,b) \in R \Leftrightarrow p\mid(a-b)$.
  2. $X = \mathbb Z \setminus \{0\}$, $(a,b) \in R \Leftrightarrow a \mid b \wedge b\mid a$.
  3. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow a \mid b \vee b\mid a$.
  4. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow \exists c\in \mathbb N: c \mid b \wedge c\mid a$.
  5. $X = \mathbb N$, $(a,b) \in R \Leftrightarrow \exists c > 1\in \mathbb N: c \mid b \wedge c\mid a$.
  6. $X = \mathbb Z\times(\mathbb Z \setminus \{0\})$, $((a,b),(c,d)) \in R \Leftrightarrow \frac ab = \frac cd$.
  7. $X = \mathcal P(\mathbb N)$, $(a,b)\in R \Leftrightarrow \text{Existuje bijekce z $a$ do $b$}$.
  8. $X = \text{Množina všech přímek v rovině}$, $(a,b)\in R \Leftrightarrow \text{$a$ a $b$ jsou rovnoběžné}$.