# I need to know the answer to this question and the best and easiest way to figure it out.A traveler stops at an inn and wants to stay for 23 days. she has no money but wants to pay with pieces from...

I need to know the answer to this question and the best and easiest way to figure it out.

A traveler stops at an inn and wants to stay for 23 days. she has no money but wants to pay with pieces from a gold chain she has. Her chain has 23 links and the innkeeper agrees to accept 1 link for each day as payment. She does not want to pay all at once so she gets the innkeeper to agree to accept payment each day so that on day one he has 1 link, and day 2 he has 2 links, and so on. The traveler does not want to give the innkeeper more than he is due on any day and she wants to cut her chain as few times as possible. What is the least number of cuts she can make and meet these conditions?

Note: Instead of just cutting a link off the end of the chain each day, the traveler can cut a link not at the end of the chain of various lengths. When she does that, the cut link becomes detatched and is single and there are two other pieces. So one cut results in three parts of chain. Also she has agreed she can give the inkeeper has the right amount of links. And than the innkeeper will accept cut rings.

Discuss your approach.

### 1 Answer | Add Yours

**On day one** she has to give him one link. There are no choice but cutting 1 link at the end of the chain.

Number of cut: 1 cut.

Chain description: 1 single link, 22 links chain

Innkeeper possession : single link

**On day 2,** she needs to give him 2 links. She may give him 2 links from the end of the chain and get the link from day 1 back.

Number of cut: 2 cuts.

Chain description: 1 single link, a 2-ring chain, and 20 links chain

Innkeeper possession : 2 chain ring

**On day 3** she may give him the link she cut on day 1.

Innkeeper possession : 2 -ring chain, single link

**On day 4** she may cut a piece of 4 links at the end of the chain and get the 3 links back from the innkeeper.

Number of cut: 3 cuts.

Chain description: 1 single link, a 2-ring chain, a 4-ring chain, and 16 links chain

Innkeeper possession : 4-ring chain

**On day 5,6,7** she is able to pay the right amount with the pieces she has.

**On day 8** she cuts a 8-ring piece at the end of the longest chain.

Number of cut: 4 cuts.

Chain description: 1 single link, a 2-ring chain, a 4-ring chain, and 2 8 rings chain

Innkeeper possession : 8-ring chain

**On day 9** she may give the single ring

Innkeeper possession : 8-ring chain, 1 single link

**On day 10** Innkeeper possession : a 8-ring chain, a 2-rings chain

**On day 11,** Innkeeper possession : 8-ring chain, a 2-ring chain and 1 single link

**On day 12** Innkeeper possession : 8-ring chain, 4-rings chain

**On day 13** Innkeeper possession : 8-ring chain, 4-rings chain, 1 single link

**On day 14** Innkeeper possession : 8-ring chain, 4 rings chain, 2-ring chain**On day 15** Innkeeper possession : 8-ring chain, 4 rings chain, 2-ring chain, singe link

**On day 16** Innkeeper possession : 2 8-ring chains

**On day 17,** Innkeeper possession : 2 8-ring chains, single link

** On day 18** Innkeeper possession : 2 8-ring chains, 2-ring chain

**On day 19** Innkeeper possession : 2 8-ring chains, 2-ring chain, single link

**On day 20** Innkeeper possession : 2 8-ring chains, 4 rings chain

**On day 21** Innkeeper possession : 2 8-ring chains, 4 rings chain, single link

**On day 22**, Innkeeper possession : 2 8-ring chains, 4 rings chain, 2-rings chain

**On day 23,** Innkeeper possession : 2 8-ring chains, 4 rings chain, 2 rings chain single link.

**In summary, she managed to pay each day what she owe in 4 cuts.** **The pieces are 2 8-rings chains, a 4-rings chain, a 2-rings chain, and a single link.**