Příklad 1. Dokažte, že prvočísel je nekonečně mnoho.
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.
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í?
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$.
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í:
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.
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.
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$".