Úloha 3.u1: Výběr čísel (3 b)

Zadáno v čísle 22.3.

Řešeno v čísle 22.5.

Zadání

Rozhodněte, jestli pro libovolných 101 přirozených čísel menších nebo rovných 200 lze vždy vybrat 2 čísla tak, aby jedno dělilo druhé.

Řešení

Rozdělíme si čísla 1, ... 200 do 100 různých množin $M_1, ... , M_{100}$, kde $k$-tý prvek množiny $M_ n$ je určen vztahem $2^{k-1}(2n-1)$. Jednotlivé množiny jsou omezené shora číslem $200$ a vypadají následovně:

\begin{align*} M_1 & = \{ 1, 2, 4, 8, 16, 32, \dots {}, 128\} \\ M_2 & = \{ 3, 6, 12, 24, 48, \dots {}, 192\} \\ M_3 & = \{ 5, 10, 20, 40, \dots {}, 160\} \\ & \vdots \\ M_{99} & = \{ 197\} \\ M_{100} & = \{ 199\} \end{align*}

Ukážeme, že každé z čísel od 1 do 200 spadá právě do jedné z definovaných množin. Pokud chceme umístit do nějaké množiny liché číslo, jedná se o nejmenší člen množiny (dané číslo můžeme rozložit na $2n-1$, z čehož získáme, že patří do množiny $M_ n$). Jestliže chceme do nějaké množiny umístit sudé číslo, víme, že se nebude jednat o nejmenší člen. Toto číslo ale můžeme vydělit dvěma. V případě, že tím získáme liché číslo, našli jsme nejmenší člen množiny, do které patří i naše sudé číslo. Pokud po dělení dvěma dostaneme opět sudé číslo, budeme ho dělit dvěma tak dlouho, dokud nedostaneme liché číslo, které je již nejmenším členem množiny. Tím je i dokázáno, že každé číslo je právě v jedné množině.

Pokud jakkoliv vybereme 101 čísel menších rovno 200 (tedy z množin $M_1$$M_{100}$), budou podle Dirichletova principu alespoň dvě čísla ze stejné množiny, tedy jedno dělí druhé.

Tím jsme dokázali, že ze 101 čísel menších rovno 200 lze vždy vybrat dvě čísla tak, aby jedno dělilo druhé.

Míša