Úlohy pro zábavu i pro poučení
Pět čísel
Lze najít pět přirozených čísel takových, že žádná jejich podskupina nedá v součet dělitelný pěti? (Např. čísla $1$, $3$, $8$, $11$, $13$ nevyhovují, protože $1+3+11=15=5\cdot3$.)
Řešení
Zkoušet různé pětice tak dlouho, dokud se netrefíme, je pracné (a jak uvídíme, také marné). Zkusíme na to jít jinak. Dělíme-li přirozená čísla pěti, dostaneme některý z pěti zbytků $0$, $1$, $2$, $3$, $4$. Podle toho můžeme všechna přirozená čísla rozdělit do pěti podmnožin; každé z nich bude právě v jedné z nich (tyto podmnožiny se nazývají zbytkové třídy). Hledaná čísla označme $a$, $b$, $c$, $d$, $e$. Podskupiny těchto čísel jsou $\{a\}$, $\{b\}$, $\{c\}$, $\{d\}$, $\{e\}$, $\{a,b\}$, $\{a,c\}$, ..., $\{a,b,c,d,e\}.$
Celkem jich je $2^{5-1}=16$ (viz též úlohu
Čísla jako součty). Nám bude stačit vzít v úvahu pět skupin $\{a\}$, $\{a,b\}$, $\{a,b,c\}$, $\{a,b,c,d\}$, $\{a,b,c,d,e\}.$ Alespoň dva z pěti výsledných součtů musejí být v téže zbytkové třídě (jde o tzv. Dirichletův princip, viz např. úlohu
Jsou v Praze dva lidé se stejným počtem vlasů?). Ozančme je $s_1$, $s_2$. Rozdíl těchto dvou součtů bude opět vyjádřen jako součet některé z podskupin skupiny čísel $a,b,c,d,e$ (např. $(a+b+c+d)-(a+b)=c+d$), tj. bude to některý z $16$ možných součtů. Ten však bude nutně dělitelný pěti. Součty $s_1$, $s_2$ totiž při dělení pěti dávají stejný zbytek, např. $r$, a můžeme je tedy vyjádřit ve tvaru $s_1=5m+r$, $s_2=5n+r$, takže $s_1-s_2=5(m-n)$.