Zadanie
Jerry s Pedrom sa zase chceli zahrať počas oslavy videohru. Na to však najprv museli rozdeliť \(17\) farebných káblov do správnych portov. Tak sa v tom zamotali až musel prísť Vodka, ktorý im prisľúbil, že im pomôže, ak vyriešia nasledovnú úlohu:
Koľko existuje prirodzených čísel \(n\), pre ktoré je číslo \(17^{2019} \cdot n\) deliteľné číslom \(17+2n\)?
Pri úlohách s deliteľnosťou sa často oplatí pozerať na prvočíselné delitele. Číslo \(17^{2019} \cdot n\) ich už na prvý pohľad nemá práve veľa (len \(17\) a delitele \(n\)), a ešte k tomu číslo \(17+2n\) má byť jeho deliteľom. Vezmime si preto nejaké prvočíslo \(p\), ktoré delí \(17+2n\). Toto prvočíslo musí potom deliť aj \(17^{2019} \cdot n\).
Ak má prvočíslo deliť nejaký súčin, musí deliť prvého alebo druhého činiteľa. Ak \(p\) delí činiteľa \(17^{2019}\), potom nutne \(p=17\). Ak naopak \(p \mid n\), potom \(p \mid (17+2n)-2n=17\), takže opäť \(p=17\).
Zistili sme, že jediné prvočíslo, ktoré môže deliť \(17+2n\) je 17, takže táto hodnota musí byť nejakou mocninou sedemnástky. Nech teda \(17+2n=17^k\) pre nejaké celé \(k\). Aby bolo \(n\) prirodzené, musí platiť \(k \geq 2\). Vyjadrením \(n\) a následným dosadením dostaneme
\[n=\frac{17^k-17}{2},\]
\[17^k \mid 17^{2019} \cdot \frac{17^k-17}{2},\]
a keďže delenie dvomi neovplyvňuje deliteľnosť \(17\), máme
\[17^k \mid 17^{2019} \cdot \left(17^k-17\right).\]
Táto deliteľnosť bude platiť práve vtedy, keď sa prvočíslo \(17\) bude nachádzať v rozklade výrazu \(17^{2019} \cdot \left(17^k-17\right)\) aspoň \(k\)-krát. Keď máme súčin viacerých činiteľov, počet výskytov prvočísla v jeho rozklade bude rovný súčtu týchto počtov pre jednotlivé činitele (prvočísla sa ponásobia dohromady).
Prvý činiteľ (\(17^{2019}\)) je deliteľný \(17\) práve \(2019\)-krát. Druhý činiteľ (\(17^k-17\)) je zjavne deliteľný \(17\) aspoň raz. Predpokladajme teraz, že by bol deliteľný aspoň dvakrát, teda by platilo \(17^2 \mid 17^k-17\). Keďže \(k \geq 2\), platí \(17^2 \mid 17^k\). Po odčítaní z toho vyplýva, že \(17^2 \mid 17\), čo však nemôže nastať.
Dostali sme teda, že bez ohľadu na hodnotu \(k\), je náš výraz deliteľný \(17\) práve \(2020\)-krát, takže si môžeme zvoliť ľubovoľné \(2 \leq k \leq 2020\) a deliteľnosť bude splnená. Naopak, pre väčšie \(k\) splnená nebude. Keďže rôzne \(k\) nám dajú rôzne hodnoty \(n\), existuje práve \(2019\) vyhovujúcich čísel \(n\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.
Hugo Bartha
Čo znená p| n? JE to to isté ako p/n?
Minh Dang Huy
Znamená to, že n delí p, teda je to len označenie pre "n je deliteľom p".
Takže to nie je isté ako p/n, čo vyjadruje podiel.
Minh Dang Huy
Minh Dang Huy
Pomýlil som sa, má to byť "p delí n" a nie "n delí p".