Zadanie
Kubko, byvší tou matematickou legendou, za ktorú ho všetci považujú, úlohu vyriešil ľavou prednou. Jótaró Hamata uznanlivo pokýval hlavou a vydali sa späť do Tokia. Sadli do Jótarovho auta a vyrazili. Jótaró chvíľu šoféroval mlčky a potom sa opýtal: „Bude ti vadiť, keď si pustím hudbu? Pri šoférovaní ma upokojuje.“ Kubko pokýval hlavou, že mu to v najmenšom neprekáža. Jótaró vybral z náprsného vrecka kazetu a vložil ju do obstarožného prehrávača. Autom sa rozľahli teplé tóny niekoho menom Takaši Jošimacu (ako Jótaró Kubkovi vysvetlil). O pol minúty na to auto zastalo a kazeta stíchla. Stáli pred Kubkovým hotelom. Nebo bolo plné hviezd, ktoré žiaľ kvôli svetelnému smogu nebolo vidieť, a noc voňala tajomstvom. Jótaró sa oprel a úplne zbytočne zašepkal: „Sme na mieste.“ Kubko prikývol a zahľadel sa na obzor. Spoločne mlčali. Jótaró napokon pootvoril ústa a potichu, ako keď kladiete niekoho srdcu blízkeho do postele, pošepkal: „To, čo ti teraz poviem, ti možno príde kryptické. Ale verím, že raz si uvedomíš plnú dôležitosť mojich slov a vtedy si na mňa spomenieš.“ Kubko nevedel, čo odpovedať, tak mlčal. Jótaró trochu bubnoval prstami po volante a napokon Kubkovi prezradil zmysel života, prezradil mu ho v otázke, ktorá Kubka mátala až do rána, a potom aj počas celého letu späť domov a ktovie ako dlho ešte:
„Existuje nekonečne veľa kladných celých čísel \(n\), pre ktoré je číslo \((2020n)!\) deliteľné číslom \(n! + 1\)?“
Ukážeme, že existuje len konečne veľa takých čísel. Predpokladajme, že pre nejaké \(n\) platí \(n!+1\mid (2020n)!\). Využitím vzťahu \[{kn\choose n}=\frac{(kn)(kn-1)\dots((k-1)n+1)}{n!}\] môžeme upraviť pravú stranu nasledovne: \[(2020n)!=(n!^{2020}){n\choose n}{2n\choose n}\dots{2020n\choose n}.\]
Vieme, že čísla \(n!+1\) a \(n!\) sú nesúdeliteľné, a preto môžeme pravú stranu deliteľnosti vydeliť \(n!^{2020}\). Dostávame \[n!+1\mid {n\choose n}{2n\choose n}\dots{2020n\choose n}.\]
Kombinačné číslo \({kn\choose n}\) sa nachádza v \((kn)\)-tom riadku Pascalovho trojuholníka, ktorého súčet je \(2^{kn}\). Preto platí \({kn\choose n}<2^{kn}\). Keď aj našu deliteľnosť nahradíme nerovnosťou, tak použitím tohto odhadu máme: \[n!+1\le {n\choose n}{2n\choose n}\dots{2020n\choose n}<2^n\cdot 2^{2n}\cdots 2^{2020n}=(2^{(1010 \cdot 2021)n})=M^n,\]
kde sme pre jednoduchosť označili \(2^{1010 \cdot 2021}=M\). Avšak faktoriál rastie rýchlejšie ako exponenciálna funkcia, a preto existuje konštanta \(C\) taká, že pre \(n>C\) je \(n!>M^n\).
Ak vám to nie je jasné, zamyslite sa nad tým, že ak položíme \(n=2M\) a postupne zväčšujeme \(n\) o 1, tak pomer \(n!/M^n\) sa vždy aspoň zdvojnásobí. Preto od istého \(C\) bude väčší ako 1.
To znamená, že nutne \(n\le C\), čo znamená, že našich hľadaných \(n\) môže byť len konečne veľa, čo sme chceli dokázať.
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ť.