8. Konštantu Mišo Stopuje vzorové riešenie

V úlohe sa nás pýtajú, koľko otázok Mišovi stačilo, aby sa číslo \(d\) dalo jednoznačne určiť. Typicky budeme dokazovať, že potrebujeme aspoň niekoľko otázok a potom ukážeme stratégiu, ktorej tento počet otázok stačí.

Začnime tým, koľko otázok potrebujeme. Najprv predpokladajme, že si Jožko vybral \(1\) a pozrime sa na prvočísla. Akým spôsobom vieme prvočíslo odlíšiť od \(1\)? Sú len \(2\) otázky, na ktoré, pokiaľ by bolo Jožkovo číslo prvočíslo \(p\), Jožko Mišovi odpovedal áno, a to „Je tvoje číslo deliteľné číslom \(p\)?“ a „Je tvoje číslo deliteľné číslom \(1\)?“, pričom iba prvá z týchto dvoch otázok dokáže odlíšiť prvočíslo od jednotky. Ak teda existuje prvočíslo \(\leq2023\), na ktoré sa Mišo nespýta, tak si nemôže byť istý, či má Jožko jednotku alebo dané prvočíslo. Prvočísel do \(2023\) je \(306\), a tak potrebujeme aspoň \(306\) otázok.

\(306\) otázok už bude stačiť. Nech \(p_i\), predstavuje \(i\)-te prvočíslo, kde \(i \in \{1,\dots, 306\}\). Potom prvá Mišova otázka bude „Je tvoje číslo deliteľné číslom \(p_1 = 2\)?“. Ďalej postupujme nasledovne. Kým Jožko odpovedá áno, Mišo zvyšuje mocninu prvočísla, na ktoré sa pýtal. To znamená, že ak na otázku pre \(d=2^1\) Jožko odpovie áno, Mišo sa opýta otázku pre \(d=2^2\). Akonáhle však Jožko povie nie na \(p_i^k\) (pričom, keďže sa ho to Mišo pýtal, tak predtým dostal odpoveď áno na \(p_i^{k-1}\)), vieme, že \(k-1\) je najvyššia mocnina, v ktorej sa \(p_i\) v pôvodnom čísle vyskytuje. Posunieme sa teda na ďalšie prvočíslo \(p_{i+1}\), ktoré preveríme podobným spôsobom.

A to je Mišova stratégia. Stačí iba ukázať, že Mišo sa za maximálne \(306\) otázok dostane k cieľu.

• Pokiaľ všetky Jožkove odpovede sú nie, potom vieme, že Jožkovo číslo nie je deliteľné žiadnym prvočíslom do \(2023\) (Mišo postupne prejde cez všetkých \(306\) prvočísel), a teda je to \(1\).

• Pokiaľ Jožko odpovie nie na prvočísla do \(\sqrt{2023}\leq 45\), potom prvá odpoveď áno je už naše hľadané číslo \(a\), lebo najmenšie zložené číslo pripadajúce do úvahy je jeho druhá mocnina (žiadne menšie nie je deliteľom \(d\), lebo odpovede boli nie). Druhá mocnina je už ale veľmi veľká – \(a^2 \geq 45^2 = 2025\). Výsledok teda bude prvočíslo \(a\), to odhalíme na maximálne \(306\) otázok.

• Pokiaľ Jožko odpovie áno na číslo do \(45\), toto číslo je aspoň \(2\), a teda číslo \(n\) nie je deliteľné žiadnym prvočíslom \(p \geq 1012\), inak by \(n \geq 2\cdot p \geq 2024\), čo nejde. Takýchto prvočísel, ktoré sú väčšie ako \(1012\), a teda sa na ne nebudeme musieť pýtať, je \(137\). Avšak Jožko nám môže povedať áno maximálne \(10\)-krát. Ak by nám povedal áno \(11\)-krát, tak by v prvočíselnom rozklade čísla \(n\) muselo byť minimálne \(11\) činiteľov, z ktorých je každý aspoň \(2\). Takže \(n\) by muselo byť aspoň \(2^{11}=2048\), čo je už príliš veľa. Bude nám určite stačiť \(306-137+10 \leq 306\) otázok, aby sme odhalili prvočíselný rozklad čísla \(n\), a tým ho jednoznačne určili.