Úloha 3.u2: Součet a součin 2 čísel (3 b)

Zadáno v čísle 24.3.

Řešeno v čísle 24.5.

Zadání

Majitel firmy určil na trezoru heslo, které tvoří dvě přirozená čísla $X$ a $Y$ tak, že platí $1 < X < Y$ a $X + Y < 100$. Dva jeho zástupci mají za úkol se v případě šéfova úmrtí sejít a uhodnout heslo k trezoru (mají na zadání hesla právě 2 pokusy, aby mohli vyzkoušet záměnu pořadí čísel). Prvnímu zástupci majitel pověděl součin těchto čísel a druhému součet.

První: „Nedokážu ta čísla určit.“
Druhý: „To jsem věděl.“
První: „Nyní už je znám.“
Druhý: „A já také.“

Jaká čísla tvoří heslo k trezoru?

Řešení

První zástupce zná součin čísel, označme jej $p$, druhý má jejich součet, označme jej $s$. Pro zjednodušení budeme rozklad čísla na dva činitele označovat jako rozklad a rozdělení čísla na dva sčítance jako rozdělení.

Z vyjádření prvního zástupce, že nemůže čísla určit, můžeme vypozorovat následující:

  • $p$ není součin dvou prvočísel
    Kdyby bylo $p$ součinem dvou prvočísel, pak by první zástupce dokázal jednoznačně určit $X$ a $Y$.

  • $p$ není třetí mocnina prvočísla
    Pokud $p = q \cdot q\cdot q$, pak existuje jen rozklad $q \cdot q^2$, jelikož $X$ a $Y$ jsou větší než jedna.

  • prvočíselný rozklad $p$ neobsahuje prvočíslo větší než 49
    Kdyby prvočíselný rozklad obsahoval prvočíslo $v$ větší než 49, tak by $p$ mělo jediný možný rozklad, a to na součin $v$ a zbytku prvočísel. Jiné rozklady nejsou možné, protože kdyby $v$ bylo v rozkladu vynásobené libovolným prvočíslem, byla by tato část rozkladu větší než 100, tím spíše by součet obou částí byl větší než 100, což je v rozporu se zadáním.

Rozklad, pro který neplatí některá z výše uvedených podmínek, nazveme jednoznačný. Součin $p$ tedy nemá jednoznačný rozklad.

Podíváme se nyní, co vyplývá z prohlášení druhého zástupce. Ten tvrdí, že se od prvního nedozvěděl nic nového. Takže víme, že pro každé rozdělení $s = a + b$ nemá $a \cdot b$ jednoznačný rozklad. Pro každé rozdělení má součin sčítanců rozklad splňující výše uvedené podmínky.

Speciálně si všimneme, jaká $s < 100$ nemají rozdělení vedoucí na jednoznačný rozklad. Dle Goldbachovy hypotézy se každé sudé číslo větší než 2 dá zapsat jako součet dvou prvočísel. Hypotéza není dokázaná, ale bylo ověřeno, že platí i pro hodně vysoká čísla. I když tuto hypotézu neznáme, tak ji můžeme pro sudá čísla menší než 100 snadno ověřit. Z lichých čísel můžeme vyškrtnout všechna ve tvaru $q + 2$ pro $q$ prvočíslo, $q \neq 2$. Právě v těchto případech budou lichá čísla součtem dvou prvočísel (součet dvou lichých čísel je číslo sudé a 2 je jediné sudé prvočíslo). Dál je $s < 55$, protože 53 je nejmenší prvočíslo větší než 49 a každé vyšší $s$ dokážeme rozdělit na $53 + (s - 53)$, kdy $53 \cdot (s - 53)$ má jednoznačný rozklad. Z vyjádření druhého zástupce máme

\[ s \in S = \{ 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53\} \hbox{.} \]

Po získání předchozí informace už první zástupce čísla $X$ a $Y$ zná. Znamená to, že $p$ má právě jeden rozklad $p = a \cdot b$, pro který $a + b$ nemá rozdělení na $c + d$ takové, že $c \cdot d$ má jednoznačný rozklad. Jinými slovy existuje jediný rozklad $p = a \cdot b$ takový, že $a + b \in S$. Číslo $p$ splňující toto pravidlo označíme jako dobré.

Mnoho práce si ulehčíme následujícím pozorováním. Pokud $p = 2^ k \cdot q$ pro $q$ prvočíslo, $k > 1$, $2^ k + q \in S$, pak je tento rozklad $p$ jediný takový, tj. není žádný další rozklad, pro který součet činitelů náleží do $S$. Tudíž každé $p$ v tomto tvaru je dobré. To plyne z toho, že každý jiný rozklad je ve tvaru $p = 2^ i \cdot 2^{k-i}q$ pro $i = {1, \ldots , k-1}$. Odpovídající součet je pak $2^ i + 2^{k-i}q$, kde jsou obě složky sudé, takže i součet je sudý a nemůže ležet v $S$.

Po druhém prohlášení prvního zástupce zná odpověď i druhý zástupce. Díky této informaci víme, že $s$ má jediné rozdělení $s = a + b$ takové, že $a \cdot b$ je dobré. Nyní projdeme všechny prvky $S$ a budeme hledat rozdělení s dobrými součiny. Chceme ukázat, že existuje pouze jeden prvek $S$, který má pouze jedno rozdělení s dobrým součinem.

Pro všechny prvky $S$ snadno najdeme alespoň jeden dobrý součin pomocí „ulehčujícího“ pozorování1:

\begin{align*} 11 & = 4 + 7 = 8 + 3\\ 17 & = 4 + 13\\ 23 & = 4 + 19 = 16 + 7\\ 27 & = 4 + 23 = 8 + 19\\ 29 & = 16 + 13\\ 35 & = 4 + 31 = 32 + 3\\ 37 & = 8 + 29 = 32 + 5\\ 41 & = 4 + 37\\ 47 & = 4 + 43 = 16 + 31\\ 51 & = 4 + 47 = 8 + 43\\ 53 & = 16 + 37 \end{align*}

Kandidáti na prvek $S$, který má jediné rozdělení s dobrým součinem, jsou $17, 29, 41, 53$. U třech z nich ale najdeme kromě již nalezeného dobrého součinu ještě další:

\[ 29 = 2 + 27 \hbox{ a } 54 = 2 \cdot 27 = 6 \cdot 9 = 3 \cdot 18 \]\[ 2 + 27 \in S~ \]\[ 6 + 9 = 15 \notin S \]\[ 3 + 18 = 21 \notin S~ \]\[ 41 = 7 + 34 \hbox{ a } 238 = 7 \cdot 34 = 14 \cdot 17 \]\[ 7 + 34 = 41 \in S \]\[ 14 + 17 = 31 \notin S~ \]\[ 53 = 10 + 43 \hbox{ a } 430 = 10 \cdot 43 = 5 \cdot 86 = 2 \cdot (5 \cdot 43) \]\[ 10 + 3 = 53 \in S \]\[ 5 + 86 = 91 \notin S~ \]\[ 5 \cdot 43 > 100 \]

Dostáváme, že pro daná rozdělení jsou jejich součiny dobré, protože právě jeden jejich rozklad má svůj součet v $S$.

Zbývá ověřit, že nalezený dobrý součin pro 17 je opravdu jediný. Jelikož $17 \in S$, stačí pro každé rozdělení 17 vzít jeho součin a pro něj najít rozklad, jehož součet také náleží do $S$:

\begin{align*} 2 & \cdot 15 = 30 = 5 \cdot 6,\hskip5.5pt5 + 6 = 11 \in S, \\ 3 & \cdot 14 = 42 = 2 \cdot 21,\hskip5.5pt2 + 21 = 23 \in S,\\ 4 & \cdot 13 = 52 = 2 \cdot 26,\hskip5.5pt2 + 26 = 28 \notin S,\\ 5 & \cdot 12 = 60 = 3 \cdot 20,\hskip5.5pt3 + 20 = 23 \in S,\\ 6 & \cdot 11 = 66 = 6 \cdot 11,\hskip5.5pt6 + 11 = 17 \in S,\\ 7 & \cdot 10 = 70 = 2 \cdot 35,\hskip5.5pt2 + 35 = 37 \in S,\\ 8 & \cdot 9 = 72 = 3 \cdot 24,\hskip5.5pt3 + 24 = 27 \in S.\\ \end{align*}

Číslo 17 má tedy opravdu jediný dobrý součin, 52, a hledaná čísla jsou 4 a 13.

Anet


1) levý sčítanec je vždy mocnina dvojky, pravý prvočíslo