Viacnásobné obliehania nevyhovovali nikomu. Bolo preto prirodzené, že kráľovná potrebovala nájsť rozumné riešenie tejto situácie. A tak sa stalo, že poverila svojich troch najlepších pomocníkov Kubka, Mariánosza a Slava, aby jej našli všetky možné riešenia. Potom by si už sama vedela poľahky vybrať to najlepšie z nich.
Nájdite všetky prirodzené čísla $n$ také, že rovnica $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$ má práve $2019$ riešení tvaru $(x,y)$, kde $x$ a $y$ sú prirodzené čísla také, že $x\geq y$.
Začnime jednoducho - vynásobme rovnicu všetkými menovateľmi. Dostávame $n(x+y)=xy.$ Označme $\delta=NSD(x,y)$. Ďalej označme $$a=\frac{x}{\delta}, \quad b=\frac{y}{\delta}, \quad c=\frac{n}{ab}.$$
Lema. $a,b,c$ sú celé čísla.
Dôkaz lemy. $a,b$ sú zjavne celé. Čo sa týka $c$, máme $$\begin{aligned} n(x+y)&=xy ,\ n\delta (a+b)&=(\delta a)(\delta b) ,\ n(a+b)&=ab\delta.\end{aligned}$$ Vieme ale že $a,b$ sú nesúdeliteľné, a teda $a \nmid (a+b) \Rightarrow a\mid n.$ Obdobne $b\mid n$, a aj spolu $ab \mid n$.
Hľadajme počet všetkých prirodzených trojíc $a,b,c$ takých, že spĺňajú nasledujúce podmienky: $$abc=n, \quad NSD(a,b)=1, \quad a\geq b. \qquad (1) \label{aaa}$$ Lema. Pre každú trojicu čísel $a,b,c$ spĺňajúcu podmienky (1) existuje práve jedna dvojica čísel $x,y$ spĺňajúca zadanie. Opačne tiež, pre každé $x,y$ spĺňajúce zadanie existuje práve jedna trojica $a,b,c$. Teda je ekvivalentné počítať počet trojíc $a,b,c$ spĺňajúcich (1) ako počítať počet dvojíc $x,y$ spĺňajúcich zadanie.
Dôkaz lemy. Platí $$\frac{1}{a\delta}+ \frac{1}{b\delta}= \frac{1}{abc} \iff \delta=(a+b)c.$$
Stačí zvoliť $x=a\delta=a(a+b)c, \quad y=b\delta=b(a+b)c$. Opačne, triviálne vieme že $x,y$ jednoznačne určujú trojicu $a,b,c$. Takže existuje jednoznačné prepojenie medzi $a,b,c$ a $x,y$.
Čo sme tým získali a čo sme vlastne spravili? Zjednodušili sme si zadanie tak, aby sme dostali nesúdeliteľné čísla $a,b$, u ktorých vieme ľahko počítať súčin – sledujte ďalej. Hľadajme teda koľko trojíc $a,b,c$ spĺňajúcich (1) existuje. Uvažujme prvočíselné rozklady. Označme
$n=p_1^{N_1}\cdots p_k^{N_k},$
$a=p_1^{\alpha_1}\cdots p_k^{\alpha_k},$
$b=p_1^{\beta_1}\cdots p_k^{\beta_1},$
$c=p_1^{\gamma_1}\cdots p_k^{\gamma_1}.$
Z prvej podmienky v (1) musí platiť $N_i=\alpha_i+\beta_i+\gamma_i$, z druhej podmienky musí byť bud $\alpha_i=0$ alebo $\beta_i=0$. Tretiu podmienku využijeme neskôr aby sme iba vydelili počet riešení dvoma.
Nech je dané $n$ (a teda dané $N_1$). Ľubovoľne si zvoľme $\alpha_1\leq N_1$. Na to máme presne $N_1+1$ možností. Ak $\alpha_1\neq 0$, tak máme jednoznačne určené aj $\beta_1=0, \gamma_1=N_1-\alpha_1$. Ak $\alpha_1 = 0$, tak máme $N_1+1$ možností čo môže byť $\beta_1\leq N_1$. Takže $N_1+1$ možností pre $\alpha_1$, $N_1+1$ možností pre $\beta_1$, spolu $2N_1+2$ možností. Pozor, možnosť že $\alpha_1=\beta_1=0$ sme započítali dvakrát, teda celkový počet možností ako sa môžu pokombiť mocniny pri $p_1$ je $2N_1+1$.
Obdobne pre $p_2, \dots, p_k$. Celkový počet možností bude teda $(2N_1+1)(2N_2+1)\dots (2N_k+1)$. Týmto sme ale našli všetky možnosti, nie len také kde $a \geq b$. Ak $a=b$ tak musí zjavne byť $a=b=1$, $c=n$ a je to iba jedna možnosť. Pre zvyšné platí $a>b$. My sme ale započítali v našich možnostiach aj tie, kde $b<a$, teda skutočný počet riešení bude
$$1+\frac{(2N_1+1)(2N_2+1)\dots (2N_k+1)-1}{2} = 2019$$ $$(2N_1+1)(2N_2+1)\dots (2N_k+1)=2\cdot(2019-1)+1=4037=11\cdot367$$
Nutne teda $N_3=\dots=N_k=0$, pretože súčin viac ako troch čísel nemôže byť 4037. Čo mimo iné znamená že $n$ bude mať maximálne dva prvočíselné delitele.
Ďalej $(2N_1+1)(2N_2+1)=11\cdot367$. Platí teda buď $N_2=0$ a $N_1=2018$, alebo $N_1=5, N_2=183$. Ak si tieto čísla dáme do definície čísla $n$, získame výsledok.
Odpoveď: Rovnica má 2019 riešení práve vtedy keď $n=p_1^{2018}$ alebo $n=p_1^5p_2^{183}$ pre ľubovoľné prvočísla $p_1,\, p_2$.
Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Intenzívny matematický zážitok v lete
Tímová matematická súťaž pre stredoškolákov
Knižnica všemožných matematických múdrostí