Zadanie
Caligula si nevedel poradiť s úlohou, tak ju zveril jeho obľúbenému konzulovi Incitatovi. Ten si s ňou ale nevie dať rady. Veď je predsa kôň! Krtko neváhal ani chvíľu a pribehol mu hneď na pomoc.
Máme \(100\) kartičiek s číslami od \(1\) do \(100\) (každá kartička má práve jedno číslo a každé číslo od \(1\) do \(100\) je na práve jednej kartičke). Z nich si náhodne vyberieme \(48\) kartičiek. Ukážte, že si vieme z týchto \(48\) kartičiek vybrať také dve, že ich súčet bude deliteľný \(11\).
Po prečítaní zadania sa zháčime, že nám predsa nebude nikto hovoriť, čo vieme a nevieme urobiť a pokúsime sa teda nájsť takú kombináciu 48 kariet, v ktorej súčet žiadnych dvoch z nich nie je deliteľný 11. Po tom, čo si tí z nás, ktorí neobľubujú teóriu čísel povzdychnú, začneme tým, že si čísla od 1 do 100 rozdelíme na skupiny podľa zvyšku po delení 11. Týchto skupín nám vznikne 11, keďže možné zvyšky sú 0 až 10.
Keďže vieme, že ak si vyberieme číslo zo skupiny so zvyškom 1, potrebujeme nejaké číslo zo skupiny so zvyškom 10 na to aby ich súčet bol deliteľný 11, môžeme si vybrať čísla tak, aby takéto kombinácie nevznikli. Skupina čísel so zvyškom 1 má 10 členov, všetky ostatné 9. Okrem toho čísla v skupine so zvyškom 0 potrebujú pár z tej istej skupiny, kým všetky ostatné potrebujú pár z jednej z ostatných skupín. Máme teda 5 párov skupín, z ktorých si môžeme vybrať z každého jednu, a skupinu s číslami so zvyškom 0, z ktorej si môžeme vybrať práve jedno číslo.
Ak teda do nášho výberu 48 kariet zvolíme skupinu so zvyškom 1, pretože má 10 členov, a štyri ďalšie skupiny po 9 členoch, budeme mať 46 kariet. Potom si môžeme ešte vybrať 1 ďalšiu kartu zo skupiny so zvyškom 0, čo nám dá 47 kariet. Avšak ktorúkoľvek ďalšiu kartu by sme pridali, určite by mala nejaký pár, a teda aj keby sme karty volili náhodne, neexistuje situácia, v ktorej by pár nevznikol.
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ť.