Pokorný roľník ide na chrbát svojej vernej kobyly, aby požiadal svoju milovanú Máriu o manželstvo. Počas dlhej cesty utrpí jeho hora nehodu, ktorá mu zabráni pokračovať v ceste. Našťastie je to blízko hostince, kde môžete získať ďalšieho koňa. Hostinský mu povie, že nebude mať kone skôr, ako po siedmich mesiacoch, takže chudobný farmár nemá na výber, ale zostať v hostinci až do príchodu zvieraťa. Carlos má 10 strieborných mincí, dosť na kúpu koňa, ale nie dosť na zaplatenie ubytovania, a preto navrhuje hostinskému nasledujúce.
Mám retiazku so 7 striebornými článkami. Na konci svojho pobytu ju doručím ako platbu za ubytovanie.
Hostinský, ktorému farmár nevyvoláva dôveru, odpovedá. Dáš mi odkaz v reťazci každý deň, keď zostaneš v mojom hostinci.
Roľník, ktorý má povesť nízkeho pracovníka, premýšľa o najlepšom spôsobe, ako prerušiť články v reťazci, aby vyhovel požiadavkám hostinského, čím umožní minimálny počet strihov.
Aký je minimálny počet škrtov, ktoré musí poľnohospodár urobiť pre reťaz, aby vyhovel požiadavkám hostinca, a ako ich má doručiť?
Riešenie
Je možné vyhovieť požiadavkám hostinského pomocou jediného rezu v reťazi nasledovne:
Ak prerušíme tretí článok v reťazci, budeme mať voľný článok plus reťaz s dvoma článkami a ďalšie so štyrmi článkami:
- Prvý deň doručíme odkaz na hostinského.
- Na druhý deň dodávame reťaz s dvoma článkami a hostinský bude nútený vrátiť odkaz, ktorý sme mu poskytli predchádzajúci deň, aby sme konečne uspokojili zaplatenie odkazu za tento deň ubytovania.
- Na tretí deň doručíme voľné spojenie, ktoré nás vrátilo deň predtým.
- Štvrtý deň dodávame reťaz so štyrmi článkami a hostinský bude nútený vrátiť uvoľnený článok plus reťaz dvoch článkov.
- Piaty deň doručíme voľné spojenie, ktoré nás vrátilo deň predtým.
- Šiesty deň doručíme reťaz dvoch odkazov a vy budete nútení vrátiť voľný odkaz, ktorý sme doručili predchádzajúci deň.
- Nakoniec siedmeho dňa doručíme uvoľnený článok a my splníme požiadavky hostinca, aby sme mohli poskytnúť odkaz každý deň, a to tým, že do reťaze urobíme jeden kus.
