Zadanie
Moreplavec Fernão de Magalhães si pred plavbou na svoju loď naložil \(100\) sudov s čerstvou chrumkavou kapustou postupne s hmotnosťami \(10,\ 20,\ 30,\ \dots,\ 1000\) kilogramov. Bohužiaľ, kapusta mu v niekoľkých sudoch skvasila, čím prišla o svoju chrumkavosť. Jeho pobočník Enrique de Malacca mu však po tom, ako sa na lodi popýtal ostatných námorníkov, čo vedia o sudoch, oznámil: „Nezúfaj, síce neviem presne ktoré sudy skvasili. Ale stále viem zo všetkých sudov vybrať \(19\) sudov s čerstvou chrumkavou kapustou tak, že spolu budú vážiť aspoň \(14\,060\) kilogramov. Dokonca bez ohľadu na to, ktoré sudy ti skvasili.“ Zistite, koľko najviac sudov mohlo Magalhãesovi skvasiť.
Vieme, že niekoľko sudov s kapustou sa pokazilo a že zo zvyšných sudov sa dá vybrať \(19\) takých, že majú dokopy aspoň \(14060\) kilogramov. Keďže nevieme ktoré sudy presne sa pokazili, musíme rátať s najhorším možným prípadom – že sa pokazili tie najťažšie sudy. Nič nám nebráni zaradom skúšať odoberať najťažšie sudy a pozerať sa, či zo zvyšných stále ešte vieme vybrať \(19\) s dostatočnou váhou.
Toto skúšanie nie je príliš náročné – vždy vezmeme \(19\) najťažších sudov ktoré sa nepokazili a pozrieme sa akú majú spolu váhu. Ak raz narazíme na situáciu kedy sa pokazilo \(n\) sudov a zo zvyšných sudov \(19\) najťažších nemá váhu aspoň \(14060\) kilogramov, vieme, že \(n\) je príliš veľké a muselo sa pokaziť menej sudov.
Skúšať zaradom všetky možnosti až kým nenarazíme na tú správnu vie byť ale celkom otrava, môžeme si to teda ešte zjednodušiť. Predpokladáme, že nastal najhorší možný prípad, teda že sa pokazili najťažšie sudy \(1000,\ 1000-10,\ \dots,\ 1000-10n+10)\). Hľadáme vlastne postupnosť \(19\) za sebou idúcich sudov \(1000-10n,\ 1000 - 10n - 10,\ \dots,\ (1000 - 10n - 180)\) so súčtom váh ktorý je väčší alebo rovný \(14060\). Túto nerovnosť vieme zapísať pomocou počtu pokazených sudov \(n\) takto:
\[(1000 - 10n) + (1000 - 10n - 10) + \cdots + (1000 - 10n - 180) \geq 14060\] \[19000 - 190n - 10 - 20 - \cdots - 180 \geq 14060\] \[17290 - 190n \geq 14060\] \[17 \geq n\]
Z toho vyplýva, že \(n\) musí byť menšie alebo rovné \(17\), preto sa mohlo pokaziť najviac \(17\) sudov.
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ť.