Podrobne

Platba hostincovi

Platba hostincovi

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.