Zadanie
Tomáš triedil trojsten bufky, keď si všimol, že dodávateľ na každú zo \(100\) bufiek dopísal identifikačné číselko od \(1\) do \(100\). Každá trojsten bufka dostala iné číslo. Avšak niektorých \(k\) bufiek už bolo predaných a tieto Tomáš nenašiel. Je možné bez ohľadu na to, ktoré bufky boli predané, vybrať zo zvyšných nepredaných bufiek \(k\) takých, že súčet ich čiselok je \(100\), ak (a) \(k=9\)? (b) \(k=8\)?
\(k=9\): Aby sme ukázali, že to nie je možné, stačí nájsť jeden prípad, pre ktorý tvrdenie neplatí. Zvoľme za vybrané čísla hneď prvých deväť čísel množiny \(\{1, 2, 3,\dots, 100\}\).
Teda môžeme vyberať z čísel \(\{10, 11, 12,\dots, 100\}\). Ak sčítame deväť najmenších čísel z tejto množiny, ich súčet bude väčší ako \(100\). Ak by sme ktorékoľvek z nich nahradili iným (väčším) číslom, ich súčet bude ešte väčší. Tým pádom sme našli prípad, pre ktorý tvrdenie neplatí. Po predaní \(9\) buffiek sa teda môže stať, že už nevieme vybrať ďalších \(9\) so súčtom \(100\).
\(k=8\): Chceme vybrať osem čísel, tak aby ich súčet bol \(100\). Nad úlohou môžeme uvažovať aj ako nad výberom štyroch dvojíc čísel, ktoré keď všetky sčítame, tak máme \(100\). Hľadajme dvojice čísel, ktorých súčet je \(1/4\) zo \(100\), teda \(25\). Takýchto dvojíc je medzi číslami od \(1\) po \(100\) až \(12\) a sú to tieto: \[\{1,24\},\{2,23\},\{3,22\},\{4,21\},\{5,20\},\{6,19\},\{7,18\},\{8,17\},\{9,16\},\{10,15\},\{11,14\},\{12,13\} .\] Keďže máme k dispozícii dvanásť dvojíc a žiadne číslo sa nenachádza vo viacerých dvojiciach, aj po odstránení ktorýchkoľvek osem čísel \(\{1,2,3,\dots,100\}\) nám ešte zostanú minimálne štyri dvojice čísel, ktorých súčet je \(25\) a teda ich celkový súčet bude \(100\). To dokazuje, že po predaní \(8\) buffiek vieme stále vybrať \(8\) buffiek, ktorých súčet čísel je \(100\).
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ť.