Find Your Name
May 13th, 2007I had a lot of thinking before deciding to include this riddle in my site. The argument for not including it, is that it is too complicated. I ended up deciding it deserves its place in my riddles section (which means I believe it is one of the most beautiful riddles ever) because, well, I think it is one of the most beautiful riddles ever. So enjoy! (but be ready for a hard one…):
There are 100 men, 100 boxes and 100 notes with the men’s names on them. The 100 boxes are arranged in a line in a room. Each of the notes with the names is put in a different box randomly. The men are put together and are allowed to decide upon a strategy. When they are done, they are taken, each in his turn, to the room with the boxes. Each one is allowed to open 50 of the boxes. No information whatsoever is shared between the men.
The goal of the men is that each of them finds his own name among the 50 boxes he opened. If but one of them fails to find his own name, they all get killed (why is it, that in so many riddles people end up dead?). You are required to find a method with which they are all saved with a probability of above 30%.
If you understood this riddle properly, it should seem impossible to you at first.
Because the riddle contains many details and to make sure I explained it properly, lets consider two bad strategies for the men:
1. All the men decide to open the same 50 boxes - this is probably the worst strategy for them, as all of them will die with probability 1. This is because 50 of them are sure not to find their names in the boxes they open.
2. Every man open 50 boxes randomly - although a better strategy than the former one, it is a very bad strategy. Each person is likely to find his own name with a probability of 1/2. As all the events of the men finding their names are independent, they will be saved with a probability of (1/2)^100.
As this number is smaller than 0.00000000000000000000000000000079 (which is obviously smaller than 30%) it is a very bad strategy indeed.
BTW - to calculate the above number I used the following python statement:
>>> '%1.32f'%0.5**100
Solution now available on next page!
Pages: 1 2
May 18th, 2007 at 9:33 am
I want to make sure about one important detail of the riddle - you said “Each of the notes with the names is put in a different box randomly” - is it truly random, or is the person arranging the names in the box allowed to be “evil” and put them in such a way as to fail the men’s strategy?
If the names are put in the boxes randomly, then I solved it!!!
What a cool riddle.
I want to comment about the solution, but is there any way to put text in spoiler tags? I don’t want to ruin the solution for people reading the comments…
May 18th, 2007 at 9:41 am
Update for my last comment. My first question was irrelevant. The same solution works even if an evil genius arranges the names in the boxes.
May 18th, 2007 at 3:24 pm
Hi Matan,
First let me congratulate you for being the first person to comment on my site.
You raised an interesting question, and I still have to decide how I want solutions to be posted. I think what I will do is publish a “solution post”, which will be password protected with a known password (such as “solution”). That way everyone will be able to see the solutions but no one will see them accidentally.
Anyway, I am going to wait for a couple of weeks since the time I publish a riddle and the time I publish its solution (otherwise the temptation to read the solution is to big).
May 22nd, 2007 at 5:32 pm
Well, without meditating on this one too much, I believe I have the algorithem. I’d ask here if I’m in the right direction, but that would be spoiling, now wouldn’t it?
guess I’ll check my constants and get back to you.
May 23rd, 2007 at 10:25 pm
Elad, a friend of mine, complained that the riddle is not that hard. Well, I might have exaggerated about the difficulity level. The puzzel is solvable. I only meant to say that it is harder than all the riddles posted before it (those of you with good perception might notice that only the Ants riddle was posted before it
).
I also like the “Warning! Very Hard!” logo, and I think I’ll keep it.
Anyways - if it is too easy for you, you can always try to solve it with 1000 men instead of 100!
November 29th, 2007 at 7:27 am
greatings
nice