Zadanie
Mr. Miro je osvedčený detektív, takže pomáha pri pátraní kombinačných čísel. Nájdite dvojicu prirodzených čísel $n$ a $k$ takú, aby kombinačné číslo $\binom{n}{k}$ bolo deliteľné tisícimi a navyše
- číslo $n$ bolo najmenšie možné,
- súčet $n+k$ bol najmenší možný.
Poznámka. Kombinačné číslo $\binom{n}{k}$ označuje počet spôsobov, ako vybrať z~$n$ predmetov $k$ predmetov, pričom nám nezáleží na poradí. Možno ho vypočítať ako $$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\dots(n-k+1)}{1\cdot 2\cdot\ldots\cdot k}.$$
Začneme hľadaním takého čísla, že \({n}\choose{k}\) je deliteľné číslom \(1000\). Jedno také je zjavne \({1000}\choose{1}\), ale nenašli by sme niečo s menším \(n\)? Aby číslo \[\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots(1)}\] bolo deliteľné \(1000\), tak musí byť v prvočíselnom rozklade čísla \({n}\choose{k}\) aj číslo \(2^{3}\cdot 5^{3}=8\cdot 125\). Najprv sa postaráme o prítomnosť súčiniteľa \(125\). Isto keď \(n=125\), tak ho tam máme, teda aspoň pri väčšine \(k\)-čok. Prichádzajú dve otázky – nemôže byť menšie? Pre ktoré \(k\), ak také existuje, už úplne vyhráme?
Vyriešme prvú otázku. Ukážeme, že také kombinačné číslo nie je. Poďme to dokazovať sporom, čiže budeme predpokladať, že také riešenie existuje a z jeho vlastností ukážeme, že v skutočnosti také nie je. Nech \(n<125\) a \(k<n\) je riešenie. Vieme, že v postupnosti prirodzených čísel je každé piate deliteľné \(5\) a každé dvadsiate piate je deliteľné \(25\). Taktiež musí platiť, že máme \(k\) súčiniteľov v čitateli a týchto \(k\) súčiniteľov, ktoré idú po sebe a začínajú na ľubovoľnom mieste, má nanajvýš \(\lceil{\frac{k}{5}}\rceil + \lceil{\frac{k}{25}}\rceil\) pätiek v prvočíselnom rozklade. V menovateli máme obdobne presne \(\lfloor{\frac{k}{5}}\rfloor + \lfloor{\frac{k}{25}}\rfloor\) pätiek v rozklade, tu začíname od jednotky. Lenže tieto čísla sa pre všetky uvažované \(k\) najviac líšia o \(2\), a teda dostávame spor s tým, že \({n}\choose{k}\) je deliteľné \(125\).
Prichádza odpoveď na druhú otázku. Uvažujme \(n=125\). Teraz chceme nájsť zodpovedajúce \(k\). Keď sa pozrieme na zopár malých \(k\) zistíme, že stále nemáme zabezpečenú deliteľnosť ôsmimi. Tu je dobré si uvedomiť, že vždy, keď zväčšíme \(k\), tak aj do čitateľa, ako aj do menovateľa pridáme číslo buď nedeliteľné dvoma, alebo deliteľné dvoma, vždy budú mať obe rovnakú paritu. Preto musíme zväčšiť \(k\) tak, aby sme do čitateľa pridali \(16\) a v menovateli iba \(2\). Vieme, že začíname u \(n=125\), čo je o tri čísla vedľa od mocniny dvojky \(128\). Tu sa môžete zamyslieť, že keď budeme čísla zväčšovať postupne, tak v čitateli naozaj narazíme na číslo deliteľné \(16\) skôr. Keď to vyčíslime, tak dostaneme zodpovedné \(k=14\). Kombinačné číslo \({125}\choose{14}\) je konečne deliteľné \(1000\).
Teraz sa pozrime na druhú časť, kde má byť \(n+k\) minimálne. Vieme, že \(125<n+k\le125+14=139\), tu by sa ponúkala hrubá sila ako vypísať všetky možnosti, avšak my také veci predsa nepotrebujeme. Poznajúc, že \(128\) je mocnina dvojky, môžeme ho skúsiť zvoliť za naše \(n\) a dosiahnúť tak lepší výsledok. Pre toto \(n\) potrebujeme zvoliť \(k\) tak, aby čitateľ obsahoval aj \(125\), teda zvolíme \(k=4\). Ľahko sa presvedčíme, že \({128}\choose{4}\) je delieteľné \(1000\).
Teraz vieme \(125<n+k\le132\). Už nám stačí ukázať, že žiadne menšie súčty nie sú. To môžeme už overiť všetkými možnosťami alebo ďalšími úvahami o \(n\) a \(k\). Pre \(n=126\) vieme zistiť rovnako ako pred tým, že najmenšie je vhodné \(k=7\). Pre \(n=127\) sa presvedčíme, že \(k\) neexistuje, pretože všetky kombinačné čísla \({127}\choose{k}\) sú nepárne. Pre \(n\ge129\) máme \(k\), ktoré zmenší skúmaný súčet, iba \(k=1\) a \(k=2\). Tie vybavíme následovne: \(k=1\) byť nemôže, pretože to potrebujeme najmenej \(\frac{n!}{(n-1)!\cdot1!}=1000\), príslušné (jediné) \(n\) je prekvapivo \(n=1000\). Pre \(k=2\) môžeme mať zmenšujúci výsledok len pri \({129}\choose{2}\), čo nie je deliteľné \(1000\).
Takže naše riešenia sú tieto: pre najmenšie \(n\) je to \({125}\choose{14}\) a pre najmenší súčet \(n+k\) je to \({128}\choose{4}\), čoho súčet \(n+k=132\).
Komentár
Vo vašich riešeniach sa občas vyskytli aj riešenia typu „však je to konečný počet možností, to sa nakódi“ (naprogramuje). Takýmto prístupom síce nájdeme vhodné hodnoty \(n\) a \(k\), dokonca aj bez veľkej námahy, ale nie je to zmyslom tohto semináru a ani tejto úlohy. Všimnite si, že táto úloha sa dala vyriešiť aj bez použitia počítača. Úvahy, ktoré sme použili, sa vám môžu zísť pri súťažiach, kde nemáte k dispozícii počítač, a taktiež aj pri úlohách, kde nemáme konečný počet možností. Preberanie všetkých možností pomocou počítača bez žiadnej myšlienky nie je to, o čo v KMS ide, preto sme ho v súlade s našimi pravidlami nehodnotili plným počtom bodov.
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ť.