Sīki

Maksājums krodziniekam

Maksājums krodziniekam

Pazemīgs zemnieks dodas uzticīgās ķēves mugurā, lai lūgtu mīļotajai Marijai laulībā. Garā ceļojuma laikā viņa kalns cieš no nepareizas darbības, kas neļauj viņam turpināt braucienu. Par laimi, tas atrodas netālu no krodziņa, kur var dabūt citu zirgu. Saimnieks stāsta, ka zirgi viņam nebūs līdz septiņiem mēnešiem, tāpēc nabaga zemniekam nav citas izvēles, kā palikt krodziņā, līdz dzīvnieks ieradīsies. Karlosam ir 10 sudraba monētas, pietiekami zirga iegādei, bet nepietiek, lai samaksātu par izmitināšanu, tāpēc krodziniekam viņš ierosina sekojošo.

Man ir 7 sudraba saišu ķēde. Uzturēšanās beigās es to piegādāšu kā samaksu par izmitināšanu.

Saimnieks, uz kuru zemnieks nerada pārliecību, atbild. Katru dienu, kad uzkavējaties manā krodziņā, jūs man piešķirsit saiti ķēdē.

Zemnieks, kuram ir zema darbinieka reputācija, domā par labāko veidu, kā sagriezt ķēdes posmus, lai apmierinātu krodzinieka lūgumus, nodrošinot minimālu izcirtņu skaitu.

Kāds ir minimālais izcirtņu skaits, kas lauksaimniekam jāveic ķēdē, lai izpildītu krodzinieka pieprasījumus, un kā viņam tos piegādāt?

Risinājums

Krodzinieka lūgumus ir iespējams izpildīt ar vienu ķēdes griezumu šādi:

Ja mēs sagriež trešo ķēdes saiti, mums būs brīva saite plus ķēde ar divām saitēm un vēl viena ar četrām saitēm:

  • Pirmajā dienā mēs piegādājam saiti uz krodzinieku.
  • Otrajā dienā mēs piegādājam ķēdi ar divām saitēm, un krodzinieks būs spiests atgriezt saiti, kuru mēs viņam iedevām iepriekšējā dienā, lai mēs beidzot apmierinātu saites samaksu par šo izmitināšanas dienu.
  • Trešajā dienā mēs piegādājam brīvo saiti, kas mūs atgrieza iepriekšējā dienā.
  • Ceturtajā dienā mēs piegādājam ķēdi ar četrām saitēm, un krodzinieks būs spiests atgriezt vaļīgo saiti plus divu saišu ķēdi.
  • Piektajā dienā mēs piegādāsim vaļīgo saiti, kas mūs atgrieza iepriekšējā dienā.
  • Sestajā dienā mēs piegādājam divu saišu ķēdi un būsim spiesti atgriezt brīvo saiti, kuru mēs piegādājām iepriekšējā dienā.
  • Beidzot septītajā dienā mēs piegādāsim vaļīgo saiti un būsim izpildījuši krodzinieka prasības piegādāt saiti katru dienu, veicot vienu griezumu ķēdē.


Video: Izlīdzinātais maksājums (Oktobris 2021).