9. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

V dome je na dlhej rovnej chodbe 100 dverí označených číslami od 1 do 100. Dvere majú špeciálne zámky, v ktorých možno neobmedzene veľakrát otočiť kľúčom v smere hodinových ručičiek. Po prvom otočení sa dvere odomknú, po druhom otočení sa zamknú, po treťom otočení sa odomknú, po štvrtom sa opäť zamknú, a tak ďalej. Na začiatku sú všetky dvere zamknuté. V noci príde postupne 100 ľudí. Prvý človek otočil kľúčom vo všetkých dverách. Druhý človek otočil kľúčom v každých druhých dverách. Tretí človek otočil kľúčom v každých tretích, štvrtý človek v každých štvrtých, a tak ďalej až nad ránom stý človek otočil kľúčom len v stých dverách. Ktoré dvere budú ráno odomknuté?

Vzorové riešenie

Opravovali: Paľo

Ako prvé si treba uvedomiť, že každý prechádzajúci hosť vymení stav dverí s číslami, ktoré delí. Napríklad hosť číslo 7 vymení stav na dverách 7, 14, 21, 28,...,98. Keďže dvere začínajú zamknuté, odomknuté budú práve po nepárnom počte zmien, t.j. budú to len tie dvere, ktoré majú nepárny počet kladných deliteľov.

Teraz sa dá postupovať dvomi spôsobmi, ukážeme si obe možnosti, pričom možnosť číslo 2 je tá "čistejšia".

Prvá možnosť - párovanie

Vezmime si ľubovoľné číslo dverí D a predpokladajme, že a delí D, symbolicky zaznačené ako a \mid D. Potom platí, že máme nejaké iné číslo b (tiež celé), také, že D = a \cdot b. Potom ale nutne platí aj to, že b \mid D. Čiže teraz sme vlastne našli dvojicu deliteľov a teda, keď obaja prejdú, stav sa nezmení (teda aspoň nie vďaka nim, z iných deliteľov sa môže).

Jediná možnosť, ako sa vyhnúť tomu, aby sa pridali dva delitele do počtu, je ak by a = b, lebo potom sa do celkového počtu pridá iba jeden deliteľ. Toto sa môže stať iba ak, pre dané D, vieme nájsť jeho odmocninu. Inak povedané, jediná možnosť ako sa dostať na nepárny počet deliteľov, je to, že číslo D je druhá mocnina iného celého čísla.

Druhá možnosť - prvočíselný rozklad

Vezmime si opäť ľubovoľné číslo D a rozpíšme jeho prvočíselný rozklad (k je počet rôznych prvočísel, ktoré delia D), t.j. D = p_1^{m_1} \cdot p_2^{m_2} \cdot \ldots \cdot p_k^{m_k}. Je známe, že teraz vieme vyjadriť počet deliteľov čísla D ako súčin: (m_1 + 1) \cdot \ldots \cdot (m_k + 1).

Súčin je nepárne číslo práve vtedy, keď je každý činiteľ nepárny. To pre nás znamená, že všetky čísla m_i sú párne. Z toho vieme, že sa dajú zapísať ako m_i = 2 \cdot n_i. Vráťme sa k nášmu prvočíselnému rozkladu D a použime známe pravidlo mocnín a^{b \cdot c} = (a^b)^c. Teda:

D = p_1^{m_1} \cdot p_2^{m_2} \cdot \ldots \cdot p_k^{m_k} \\ D = p_1^{2 \cdot n_1} \cdot p_2^{2 \cdot n_2} \cdot \ldots \cdot p_k^{2 \cdot n_k} \\ D = (p_1^{n_1})^2 \cdot (p_2^{n_2})^2 \cdot \ldots \cdot (p_k^{n_k})^2 \\ D = (p_1^{n_1} \cdot p_2^{n_2} \cdot \ldots \cdot p_k^{n_k})^2

To ale znamená, že číslo D je druhá mocnina a to sme presne chceli.

Odpoveď: Čísla dverí, ktoré sú ráno otvorené, sú druhé mocniny celých čísel do 100, t.j. 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Komentár

Väčšina stratených bodov plynula z toho, že ste skočili priamo od nepárneho počtu deliteľov k druhým mocninám, prípadne ste druhé mocniny nikde ani nespomenuli. Môj preferovaný typ riešenia je spôsob číslo 2, ale uznával som aj to, keď ste len spomenuli a rozumne naznačili "párovanie" deliteľov.