Matematika pro poučení i pro zábavu

Nedělejte si starosti ohledně vašich potíží v matematice. Můžu vás ujistit, že ty moje jsou ještě větší.
Albert Einstein v dopise středoškolačce Barbaře Lee Wilsonové 7. 1. 1943

Matematika je krásná: Co bylo pravda včera, je pravda i dnes.
Jaroslav Kurzweil při převzetí České hlavy v r. 2006

Úlohy pro zábavu i pro poučení

Mocniny tří

S přirozenými čísly lze provádět různá "kouzla". Zkuste dokázat, že pro každé přirozené číslo

$n$ existují taková dvě přirozená čísla

$r$ ,

$s$ , že číslo

$3^r-3^s$ je dělitelné číslem

$n$ .
Tato úloha byla zařazena do přípravného kola 30. ročníku Matematické olympiády v kategorii B pro studenty středních škol.

Řešení

Řešení je založeno na užití tzv. Dirichletova přihrádkového principu (někdy se mu také říká holubníkový princip), který říká, že když umístíme

$m$ předmětů do

$n$ přihrádek, kde

$m > n$ , pak bude existovat alespoň jedna přihrádka, ve které budou alespoň dva předměty. Dělíme-li nějaké přirozené číslo

$k$ číslem

$n$ , pak zbytek bude některé z

$n$ čísel

$0$ ,

$1$ ,

$2$ ,

$3$ , ...,

$n-1$ . Přirozených čísel

$3^1$ ,

$3^2$ ,

$3^3$ , ...,

$3^n$ ,

$3^{n+1}$ je

$n+1$ , takže aspoň dvě z nich musejí mít stejný zbytek

$z$ při dělení číslem

$n$ . Nechť jsou to čísla

$3^r$ ,

$3^s$ . Platí tedy

$3^r=pn+z$ ,

$3^s=qn+z$ , kde

$p$ a

$q$ jsou celá nezáporná čísla. Odtud dostaneme

$3^r-3^s=(p-q)n$ , což znamená, že

$3^r-3^s$ je dělitelné číslem

$n$ .