Opravovatelia

Mati [email protected]

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.