I detaljer

Betalingen til krovært

Betalingen til krovært

En ydmyg bonde går på bagsiden af ​​sin trofaste hoppe for at spørge sin elskede Mary i ægteskab. I løbet af den lange tur lider hans beslag et uheld, der forhindrer ham i at fortsætte med turen. Heldigvis er det nær kroen, hvor du kan få en anden hest. Krovært fortæller ham, at han ikke vil have heste før efter syv måner, så den fattige landmand har intet andet valg end at blive i kroen, indtil dyret ankommer. Carlos har 10 sølvmønter, nok til at købe hesten, men ikke nok til at betale for indkvarteringen, så han foreslår følgende til krovært.

Jeg har en kæde på 7 sølvkæder. Ved slutningen af ​​mit ophold vil jeg levere det som betaling for indkvartering.

Krovært, som landmanden ikke inspirerer til, svarer. Du vil give mig et link i kæden hver dag du overnatter på min kro.

Bonden, der har et ry som en lav arbejdstager, tænker på den bedste måde at skære båndene i kæden for at imødekomme kravene fra krovært, hvilket gør det minimale antal nedskæringer muligt.

Hvad er det mindste antal nedskæringer, som landmanden skal foretage til kæden for at imødekomme kravets gæster, og hvordan skal han levere dem?

Opløsning

Det er muligt at imødekomme anmodninger fra krovært med et enkelt snit i kæden som følger:

Hvis vi skærer det tredje led i kæden, vil vi have et løst led plus en kæde med to led og et andet med fire led:

  • Den første dag leverer vi et link til kroværten.
  • Den anden dag leverer vi kæden med to forbindelser, og krovært vil blive tvunget til at returnere det link, vi gav ham den foregående dag, så vi endelig tilfredsstiller betalingen af ​​et link for den dag af indkvartering.
  • På den tredje dag leverer vi det løse link, der returnerede os dagen før.
  • På den fjerde dag leverer vi kæden med fire led, og krohaveren bliver tvunget til at returnere det løse led plus kæden med to led.
  • På den femte dag leverer vi det løse link, der returnerede os dagen før.
  • På den sjette dag leverer vi kæden med to links og bliver tvunget til at returnere det løse link, som vi leverede den foregående dag.
  • Endelig på syvende dag vil vi levere det løse led, og vi vil have opfyldt kravene fra krovært om at levere et link hver dag, hvilket gør et enkelt snit til kæden.