1. Kapusta Magalhãesovi Skvasila vzorové riešenie

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.