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.