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.
Easy, just the time it too to read it.
I mean took!
Too easy.
Got the answer while reading the question.
One of the easier ones – about 10 seconds.
while reading it 🙂
“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.
The washing up
> “The washing up”
Sexist!
What would be a non-sexist job she could do?
How is that sexist!?
.. and the hoovering
15 seconds
Got it while reading, checkin took a bit longer
Later on yesterday, I found that my answer was wrong!!!
I think lots of you will have a surprise on monday!
Right off th ebat
I hope there are no programmers who fail to get this…
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.
What about people who kind of understand it?
Was goin to say the same, Simon 😉
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)
This one is too obvious.
About 20 sec. (Thought I had it in 10, but then…)
Erm .. ok, I say I got it while reading it but in fact I got it before I clicked the link to the blog … hah … beat that!
I got it before the question was even invented
I got the answer in 2346 AD
Derren, you’re so hipster!
I don’t have the answer, could you to send me the ‘link’ for this though!!!
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.
Seemed so obvious that I had to check to be sure I hadn’t missed something. Agree with Adam.
Started to write down the different possibilities, it dawned on me pretty quickly… 20-30 seconds maybe?
These puzzles are getting too easy. Try as I might I can’t even think of anything to argue about with this one.
The only possible thing to argue over might be that the hotl owner agreed to “give back the three JOINED links”?
Stu
I took the “three joined links” statement to be integral to the puzzle rather than a misdirection.
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
“…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!!
Had the answer before I finished reading.
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?).
Brute force? Are you suggesting that if she simply rips the chain apart no cuts are required?
floor(log2(n))
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
Took a moment. Thought I had the answer straight away, but then realised that it could be done in even less cuts.
Another programmer here, I agree with Adam as well.
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…
Got in in under a minute, but still think this is a nice puzzle.
i thought i solved it immediately , but the answer was wrong . the correct answer took 2 minutes.
Lets see if I have it, I think I do 🙂
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
Gold is easy to bend.
Think I have it (while reading.)
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,
> “we know from the puzzle question the hotelier keeper has that”
Nope. That was just an example.
but for the example to be possible it must be real. so my logic from there is i think correct,
got it in five minutes, very good puzzle, but easier than your others!
Ah – simontaylor’s “there are 10 types of people” reply to another comment obviously gives the generalised solution for any number of nights.
Ahhhh, a binary problem…..
There are 10 types of people in this world, those that understand binary, and those that don’t……
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….
: )
thought i had the solution instantaneously, but looking at the chain … i realized i expected too much cuts…
simple, a nice puzzle
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.
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…)
If I got it right, it took about a min to get.
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.
Don’t worry Eddie. It is yet another badly worded question
I often struggle with these puzzles, but I got this one in a few seconds.
i worked it out before i’d finished reading the question.
Got it, the solution just falls out if you do a pen and paper simulation.
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.
Got “an” answer really quick, and then a few minutes later realised I could refine it. Pretty sure my method will be allowed.
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…
I dont get the references to binary but i got the correct solution instantly. The giving change part is vital to the solution.
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 …)
Me too.
if it was 31 or 63 pieces it would have fallen off her wrist
By the way, there are 10 types of people in this world, those that understand binary, and those that don’t……
00110110101110011010001010010101 10011010101010010111100110101100 10100101011010010111100110100101
(ROFL)
To all Star War fans out there … May the 4th be with you
An oldie but still a goldie. It works on so many Leias
Faster than anyone else. Much much faster.
Got it as soon as I saw the photo and the “The 7 links” text. Didn’t even have to read the story.
A couple seconds.
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 🙂
10 seconds.
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.
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.
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!
Re-read in case I missed something. At least now I get the binary reference.
Got it ebfore getting to the end….only ’cause I’ve heard it before!
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.
About 2 seconds. Obvious if you think in binary.
About 30 seconds.
i got this before i clicked on the link to read it :smug:
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?
Some of them are always right – even when they are not!
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.)
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
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.
“(I doubt this is the answer, but if it is, I apologize.)”
Well if it isn’t it’s a darn good one.
It all depends if she has to pay in advance or can pay just before she leaves the Hotel.
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.
I got a wrong answer almost instantly, then did some mental juggling and settled on what I think is the correct one.
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
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.
an easy dynamic programming problem…i don’t think any programmer can miss this one…got it in 5 seconds..
ten seconds
Everyone here has super faster minds and wide open mouths. Come on! you are all like “I solved it before even opening my browser”
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.
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.