V detailu

Platba hostinskému

Platba hostinskému

Pokorný rolník, jde po zádech své věrné klisny a žádá manželku o svou milovanou Marii. Během dlouhé cesty trpí jeho hora neštěstí, které mu brání pokračovat v cestě. Naštěstí je to blízko hostince, kde můžete získat dalšího koně. Hostinský mu řekne, že nebude mít koně až po sedmi měsících, takže chudý zemědělec nemá jinou možnost, než zůstat v hostinci, dokud nepřijde zvíře. Carlos má 10 stříbrných mincí, dost na to, aby si koupil koně, ale ne dost na to, aby zaplatil za ubytování, a proto hostinský navrhuje následující.

Mám řetěz 7 stříbrných článků. Na konci mého pobytu ji doručím jako platbu za ubytování.

Hostinský, kterému zemědělec nevzbuzuje důvěru, odpovídá. Dáte mi odkaz v řetězci každý den, kdy zůstanete v mém hostinci.

Rolník, který má pověst nízkého pracovníka, přemýšlí o nejlepším způsobu, jak přerušit články řetězu, aby vyhověl požadavkům hostinského a umožnil tak minimální počet škrtů.

Jaký je minimální počet škrtů, které musí zemědělec provést v řetězci, aby vyhověl požadavkům hostinského a jak by je měl doručit?

Řešení

Je možné vyhovět požadavkům hostinského s jediným řezem v řetězci takto:

Pokud vyřízneme třetí článek v řetězci, budeme mít volný článek plus řetěz se dvěma články a další se čtyřmi články:

  • První den doručíme odkaz hostinskému.
  • Druhý den dodáváme řetěz se dvěma články a hostinský bude nucen vrátit odkaz, který jsme mu dali předchozí den, abychom konečně uspokojili platbu za odkaz za daný den ubytování.
  • Třetí den doručujeme uvolněný odkaz, který nás předchozí den vrátil.
  • Čtvrtý den doručíme řetěz se čtyřmi články a hostinský bude nucen vrátit volný článek plus řetěz dvou článků.
  • Pátý den doručíme volný odkaz, který nás předchozí den vrátil.
  • Šestý den dodáme řetěz dvou článků a budeme nuceni vrátit volný článek, který jsme doručili předchozí den.
  • Nakonec v sedmý den doručíme uvolněný článek a splníme požadavky hostinského, aby každý den provedl jeden řez řetězem.