A woman arrives at a hotel.  She has no money, but does have a gold chain containing 7 links (like the one in the photo, but gold).  She does not know how long she is going to stay, but offers to give one link for each night she remains in the hotel.  However, the links are tricky to saw and so the woman wants to make the smallest number of cuts possible .

The hotel owner is happy with this, and agrees to be helpful by exchanging links (so if, for example, the woman has given him three joined links in the past, she can pay for an extra night by giving him four joined links and he will give back the three joined links).

What is the smallest number of cuts that will allow the woman to pay night on night?

As ever, please do NOT post your answers, but do say if you think you have solved the puzzle and how long it took. Solution on Monday.

I have produced an ebook containing 101 of the previous Friday Puzzles! It is called PUZZLED and is available for theKindle (UK here and USA here) and on the iBookstore (UK here in the USA here). You can try 101 of the puzzles for free here.

108 comments

  1. “She does not know how long she is going to stay” I don’t know what she’ll do if she stays eight nights, though.

    1. Later on yesterday, I found that my answer was wrong!!!

      I think lots of you will have a surprise on monday!

    1. Of course, as I’m sure you know, there are 10 types of people in the world.

      Those who understand binary, and those who don’t.

    2. I ordered a book off Amazon “111 things to do in Binary”. When it arrived, I was disappointed to see that it only had 7 pages. (Hint to the answer)

  2. I have the answer and it took me 3 minutes. This statement I believe to be true until Monday when, as always, I read the solution, have a face-palm moment, realise I have nothing like the right answer and go on for another week feeling stupid.

  3. Started to write down the different possibilities, it dawned on me pretty quickly… 20-30 seconds maybe?

  4. These puzzles are getting too easy. Try as I might I can’t even think of anything to argue about with this one.

    1. The only possible thing to argue over might be that the hotl owner agreed to “give back the three JOINED links”?

    2. Stu
      I took the “three joined links” statement to be integral to the puzzle rather than a misdirection.

    3. Stu,
      Have now Googled the puzzle and see where you are coming from. The “three joined links” bit makes this a different puzzle from the classic one.
      I was wrong – there is something to argue about on Monday.
      TMT

    4. “…the three joined links….” is only an example of a possible exchange; put in for clarification. I didn’t take it to mean that as part of the answer there must be a 3 link section; although there could be!!

  5. Moments – but by ‘brute force’ still thinking if there is a generalised solution for any number of nights (i.e. if she knows she may stay up to to n nights and therefore has a chain of n links, how many cuts does she need?).

    1. Sorry for a replying to an old puzzle. On the bright but nobody should care if I post a general formula to solve, for any length chain. But seeing a wrong solution here really bothered me: “floor(log2(n))” is very wrong, and does not work even for the original puzzle.

      Here is the general solution:

      The maximum chain length (that can be handled as the puzzle describes) for a given number of cuts (n) is:

      (n+1)*2^(n+1)-1=max_links — for n cuts

      The length of each cut chain segment is then

      (n+1)*2^k, where K iterates from 0..n, with the last chain segment containing any leftovers (needed if the chain length is not exactly one of the max lengths). Of course every cut produces a single loose link.

      I wrote a program to implement this algorithm, for chain lengths of up to 2^63-1

      Reference: http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/chain-link-pay

  6. Took a moment. Thought I had the answer straight away, but then realised that it could be done in even less cuts.

  7. Well I have the answer, it took me longer than it should because I thought I had the right answer quite quickly. In fact whilst I had the right number of segments straight away it took some talking over to realise that there was a second part of the puzzle…

  8. If it is difficult to cut, I assume it is difficult to bend.
    When you separate a link is that one cut or two cuts ?
    The answer you provide could be double what you thought

  9. if there is one section of length three (because we know from the puzzle question the hotelier keeper has that), then we need investigate only more cuts needed in the remaining four.

    this gives us an upper bound of five cuts (the one that has already happened, and then the four to make the four links minimal), is easy to see the actual number can be less in these conditions,

    1. > “we know from the puzzle question the hotelier keeper has that”

      Nope. That was just an example.

    2. but for the example to be possible it must be real. so my logic from there is i think correct,

  10. Ah – simontaylor’s “there are 10 types of people” reply to another comment obviously gives the generalised solution for any number of nights.

  11. Ahhhh, a binary problem…..

    There are 10 types of people in this world, those that understand binary, and those that don’t……

  12. Note to self…. Read all of the previous posts BEFORE posting yourself. The you won’t repeat someones joke….

    BTW, Bought a book yesterday, ‘1001 Interesting Binary Facts’. Disappointed it only had 9 pages….

  13. thought i had the solution instantaneously, but looking at the chain … i realized i expected too much cuts…

  14. Not so quickly solved for me. I thought it was obvious that to split the chain in half you had to saw one link, therefore making it unusable. So I worked out a solution which allowed the woman to stay a maximum of 5 nights.
    Seeing that it was so obvious for everyone, I figured out the problem actually means that you can just split the chain and repair the broken link. In that case, yeah, with 111b links, this is indeed obvious.

  15. Pencil and paper, took a couple of minutes. BTW and FWIW my take on the “three joined links” is that it’s a statement of principle only, rather than a required stage in the solution (which surely would be impossible as it suggests the first cut is into a three and a four so how can she pay for the first night…)

  16. The wording of this puzzle is so confusing that just reading it gives me a nauseous feeling in the pit of my stomach. No idea what he’s on about. Couldn’t even begin to solve it.

  17. the solution took just a few seconds. it took a little longer to realize that richard’s example (“if, for example, the woman has given him three joined links in the past, she can pay for an extra night by giving him four joined links and he will give back the three joined links”) cannot ever happen.

  18. Got “an” answer really quick, and then a few minutes later realised I could refine it. Pretty sure my method will be allowed.

  19. I’m not sure how relevant the giving change part is, but based on the first part alone, assuming that once you’ve cut a link you can bend it sufficiently to remove it from the links on either side, I’ve got one possible solution, together with the formula for if she had a chain of n links.

    Of course, all the binary comments suggest I may have over-estimated the number of cuts needed…

    1. I dont get the references to binary but i got the correct solution instantly. The giving change part is vital to the solution.

  20. This may end up like the dreaded math theacher who made the question “If a person uses 1 minute to cut a plank in two, how long time does he need to cut it in three?” and claimed that the answer was 1,5 minutes, using the logic 1/2*3 … Oh, and btw, thinking a bit more, I understood why the chain was 7 pieces and not 15 (or 31 or 63 or …)

  21. By the way, there are 10 types of people in this world, those that understand binary, and those that don’t……

  22. 00110110101110011010001010010101 10011010101010010111100110101100 10100101011010010111100110100101

    (ROFL)

  23. Got it as soon as I saw the photo and the “The 7 links” text. Didn’t even have to read the story.

  24. Oh, that’s a clever one, thanks 🙂 Was rather surprised to find the answer falling instantly into place, so, considering time double-checking, I reckon maybe fifteen or twenty seconds to get it and confirm it 🙂

  25. It took me about 2 minutes to get an answer. I revised it downward as I worked it out.

    My only confusion is the multiple references to binary and programmers in the comments here.
    As a programmer myself, I can’t see how my solution relates to binary.

    I can see a sort of connection between binary and the direction my first solution was heading in, which makes me suspect that quite a few people have the wrong answer, because my final solution needs fewer cuts than that method would have.

    1. On reconsidering, I realise that my solution does conform to the “binary” description, however, as someone else has said, there’s a “twist” (not a hint) and the solution I have uses fewer cuts than the straightforward solution.

    2. Ah, just seeing this I’ve gone back and realised I was thinking in terms of number of pieces not number of cuts so my revised solution actually took about 24h rather than 24s!

  26. Got it as soon as I glanced at the question, read all the comments, wondered if the comments were all serious, wondered what binary meant in this context, read the question properly, decided on the answer, decided it was too obvious to be a RW solution, couldn’t work out a better solution, gave up.

    Total time 35 minutes wasted life. Realized principle of not wasting life involved reading question, solving it, ignoring wacky comments, ignoring feeling that it cant be that easy, waiting till Monday, and having the pleasure of realizing answer too subtle for me ever to have got it.

    Total wasted time zero.

  27. As always a puzzle with a twist. Get the binary reference, and the Star Wars as well. Not being allowed to post the answers, makes me curious about something: how many that claim to know the answer each week are actually right?

  28. Um… feel free to lambast me if I’m being dumb… but why doesn’t she just give him the whole chain and then make a single cut whenever she leaves?

    (I doubt this is the answer, but if it is, I apologize.)

    1. Zach
      Don’t wish to give a spoiler to distress all of the binary fans, but your answer is the only answer consistent with Richard’s question and example (as opposed to the classic version of this question).
      Chris above at 4/5/12 10.31am seems to have a similar view.
      TMT
      TMT

  29. I think I got this one in under a minute. I assume that she will stay a maximum of seven nights, but may stay less.

  30. “(I doubt this is the answer, but if it is, I apologize.)”

    Well if it isn’t it’s a darn good one.

    1. What a sensible thing to ask!! Forgive me for drawing it to attention, but common sense is as rare as hen’s teeth in these parts.

  31. There are two types of people in this world:-
    1. Those who solve this simple puzzle easily in a few seconds and
    2. Those who bang on about binary, programming and Star Wars to the complete mystification of Group 1

    1. There are 3 actually:-

      1. Those who solve the puzzle and are happy.
      2. Those don’t solve the puzzle but are happy anyway.
      3. Those who solve the puzzle and are not happy until they’ve used the opportunity to tell everyone here how brilliant they are.

  32. an easy dynamic programming problem…i don’t think any programmer can miss this one…got it in 5 seconds..

  33. Everyone here has super faster minds and wide open mouths. Come on! you are all like “I solved it before even opening my browser”

  34. Actually the question says clearly she has to pay as she goes, each night: “What is the smallest number of cuts that will allow the woman to pay night on night?”

    Of course, night on night means night after night. Though the misuse of the word “on” suggests that other parts of the question may be misworded too. Cant see anything though.
    Since the time is 7 am in London I will venture you need two cuts at one and then two more. That allows each number of nights from one to seven to be paid with exchanges – 1, 2, 2+1, 4, 4+1,4+2, 4+2+1.
    Since that is too easy, there must be some tricky, too clever by half way of doing it with one cut, but that remains for RW to spring on us on a few minutes.
    If he can’t, then all the “I did it before I finished reading” commentators have nothing much to preen themselves for.

    1. The word “misworded” is very well chosen here. Richard is very good at misdirection – see the famous diamond window puzzle from a week ago, but this question is just poorly written.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s