8. príklad - Vzorové riešenie

Zoberme si situáciu kde najmenšie závažie nie je 1 . V tejto situácii dokážeme od každého závažia odčítať nejaké kladné celé číslo k , menšie ako najmenšie závažie. Toto môžeme spraviť, lebo pri každom porovnávaní máme na oboch stranách 2 závažia, takže od oboch strán odčítame hmotnosť 2k , čo nám nezmení výsledok porovnania. Nie len, že nám to nezmení porovnávania, ale aj nám to zmenší najväčšie závažie. My chceme zaistiť čo najmenšie najväčšie závažie, takže najmenšie závažie je 1 . Už vieme že najmenšie je 1 , tak druhé najmenšie bude 2 , lebo je to druhé najmenšie kladné celé číslo.

Aby to platilo pre ľubovoľnú štvoricu závaží, musí to platiť pre najhorší možný prípad. Tento prípad nastane keď budeme mať na jednej strane najťažšie závažie ( z ) s najlahším závažím (ktoré už vieme, že je 1 ), a na druhej strane druhé ( x ) a tretie ( y ) najťažšie závažia. Zo zadania vieme, že strana s najtažším závažím musí byt väčšia, tak si dajme túto situáciu do nerovnice.

x + y \lt z + 1

Keďže rátame s kladnými celými číslami tak najmenšie z , ktoré vyhovuje tejto nerovnici je x + y . To znamená, že najťažšie závažie musí byť súčtom druhého a tretieho najťažšieho závažia, druhé najťažšie súčtom tretieho a štvrtého najťažšieho, atď. Prípomína vám toto niečo? Áno, je to Fibonnaciho postupnosť!

Z tohoto si môžeme uvedomiť že i-te najlahšie závažie je i-ty člen Fibonnaciho postupnosti, pričom prvé dva členy sú 1 a 2 . Najťažšie závažie je vlastne 12-te najlahšie, čize 12-ty člen Fibonacciho postupnosti. Tento člen vieme zistiť napríklad tak, že si všetky členy do 12-teho vypíšeme.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

Odpoveď: Najmenšia hmotnosť najťažšieho zo všetkých závaží môže byť 233 .

Komentár

Skoro všetkým z vás chýbal riadny dôkaz na to, že najmenšie závažie je naozaj 1. Dalo by sa to považovať za chybu, ale rozhodli sme sa, že tentokrát za to nebudeme strhávať body, no dávajte si nabudúce pozor.

Tento dôkaz bol dôležitou súčasťou správneho riešenia, lebo síce teraz bolo správne riešenie zjavné ale nie vždy tak tomu je.