Subscribe via feed.

100 mathematicians and 100 boxes

Posted by Karys on April 7, 2011 – 1:36 am

100 mathematicians are challenged to a deadly game. There is a room into which there are 100 boxes numbered from 1 to 100, each of them containing the name of 1 of the 100 mathematicians. (so that each name is contained in a box, and we assume that no two mathematicians have the same name)

The mathematicians are to go into the room one after the other has come out. Once inside, each of them will have to open at most 50 boxes, in any order, until they find their name. They are not allowed to change the places of the names, nor can anyone who comes out of the room give any information on the contents of the boxes to his fellow mathematicians. If one has not found his (why not her ?) name, all 100 mathematicians instantly die.

The mathematicians are allowed to agree upon a common strategy before beginning the game, is there any way they can improve their chances of surviving ?

This post is under “Logic, MathsChallenge” and has 115 respond so far.

115 Responds so far- Add one»

1. 1. Noman Nadeem Butt Said：

all of them should open last 50

2. 2. Noman Nadeem Butt Said：

50 0f them will find their names if they open same 50 either first or last any 50 they are agreed upon

3. 3. Chris Said：

There are many strategies they could use. The simplest is that each just opens box 1, that way they can get it over with quickly.

***************************************
SOLUTION(s): This note was added 3rd May 2013
***************************************
Post 37, for Karys’s solution.
Post 67, for info (by slavy).
Post 74, for the probability theory (also by slavy).
Post 114, for an excellent and thorough article by Deelit.

4. 4. slavy Said：

Hi, Chris. I assume Karys wants the best strategy, which is unique (up to permutation of the boxes, of course)

5. 5. Euclid's Brother Said：

hm.. according to this statement…

“If one has not found his (why not her ?) name, all 100 mathematicians instantly die.”

Then the first person has a 50/50 chance of finding his name. If he doesn’t, they all instantly die.

If the first person DOES find his name, then the second person has to go in.. and if he doesn’t find his name, then they all intantly die. etc etc.

So.. there overall chance of getting through all 100 and all of them having found their name is 7.8886090522101180541172856528279e-29% chance.

I hope my brother isn’t in that group..

Perhaps I’ve misunderstood the problem.

6. 6. Chris Said：

Perhaps I have misunderstood the question. I thought it was too easy.

This reminds me of another problem involving hats. But in that one, the victims (who was tied to a stake) announced the colour of their hat. But the posted problem doesn’t say when or how they let the world know that they have or haven’t found their name.

7. 7. Karys Said：

So, uh, seems like I wasn’t so clear at all ^^

(BTW how do you edit the problems ? Do I need to contact anyone ?)
However, Euclid’s brother has understood it quite well, except that the probabilities are not 50/50 for each one.

So, let me reformulate the problem : Let’s call the mathematicians with their numbers,
Number 1 enters the room.
a) Number 1 opens a box.
b) If his name is not in it,
i) if Number 1 has not opened 50 boxes yet, he can (must) open another one, repeat from a).
ii) if that was the 50th box, all 100 mathematicians die.
c) If his name is in it, he can go out (without asking too much about, like, how the game master knows whether they have found their name or not ) and Number 2 goes in and do the same as Number 1 from a).

If all 100 mathematicians found their names, they can then leave relaxed… or will they ?

8. 8. Karys Said：

Uh actually looks like I was wrong and Euclid’s brother was right on the probability of 50% whith the random box strategy.
But I was told there’s at least one better strategy…

9. 9. DP Said：

I’m assuming that the boxes can’t move. So…it’s not like every person can open 50 boxes even if they have already found their name, and work on puting everything in alphabetical order. You said they can’t change names, but nothing about the boxes. I should assume that we cannot re-arrange the boxes out of numerical order though.
Yeah, Chris..the way you answered in post #1 makes me think you were trying to kill them all off as fast as possible. If that is the case, they should all open the same 50 boxes. By the 51st person they should all be dead.

10. 10. Chris Said：

Hi DP. I read the question as meaning that if at least one found their name, they were off the hook.

11. 11. Wizard of Oz Said：

If I’ve got this right then it seems to me that the best strategy for the mathematicians (M’s) would be for them to alternately examine half the boxes (say 1-50), then the other half (say 51-100).

The following scenario then assumes each M is successful in finding his/her name, otherwise game end.

M1 finds name in boxes 1-50 with probability 50/100.
M2 finds name in boxes 51-100 with probability 50/99, since one box in the first 50 has M1’s name.
M3 finds name in boxes 1-50 with probability 49/98 since one box in each group has M1 and M2’s names.
M4 finds name in boxes 51-100 with probability 49/97.
. . . and so on.

The idea being that the even numbered M’s have a slightly better than 50% chance of finding their name in boxes 51-100 because an extra box has been successfully picked in the other group by the preceding odd-numbered M’s. The odd numbered M’s still have exactly 50% chance of finding their names, but the overall group chance of survival is still better than if each M picked boxes at random.

So, the chance of all 100 surviving under this scenario is:
50/100 * 50/99 * 49/98 * 49/97 * . . .
= (50!)^2/(100!) = 9.9 x 10^-30

Still not good, but better than the chance of survival from random picking, which would be:
2^-100 = 7.9x 10^-31.

12. 12. Karys Said：

With this I realize how hard it is to try to set all rules for a game ^^
So DP was right assuming neither boxes nor names could be moved like to leave a message to next mathematicians.

Each “player” has to have found his name for everybody to be free.

If one has found his name, he cannot tell anyone, nor will the corresponding box be removed, so the next participant may open a box containing the name of previous participants.
In fact, what each mathematician does in the room is independent of what others will do or have done previously.
The goal here is maximizing the chance of each one to find the box in which his name is written.

13. 13. twall Said：

Do you have to close the box again after the first person opened it?

14. 14. John24 Said：

No matter what strategy the Mathematicians apply, they only have a 50-50 chance to survice the 1st Mathematician’s effort.

Assuming they survive this 1st M’s attempt here is my strategy.

M1 enters and opens box 1 and writes the name on the box. Opening up to 50 boxes as required and writing the name on the box.

M2 simply opens up to 49 other boxes and writes the names on the boxes as well. If he has not found his name by box 49 then reads each name on M1’s boxes either finding his name or not. If not, then his name is in one of the remaining boxes and must guess.

M3 repeats what M2 did.

This goes on until either they die or all 100 boxes have a name on them. Once there is a name on all boxes they have defeated the game.

Another option would be to leave an item on the box if it contained their name allowing the rest of the mathematicians to skip that box.

If they can’t write or alter the boxes in any manner, then I can’t see anyway they can improve their odds.

Wait, what if they took an exact amount of time at each box, say 1 minute. If Mathematician finds his name he leaves the room immediately and his fellow mathematicians know that if he was in the room for 11 min x seconds then his name was in box 11 and they can skip that box, increasing their chance of surviving greatly.

15. 15. Chris Said：

I like John24 timing trick.

The rules don’t specifically say that the boxes have to be closed – but I think that was an oversight.

However, the rules don’t say that you can’t rotate a box. If so, the first man puts all the boxes into an agreed on orientation. Then s/he opens the boxes and re-orients them to indicate the place in the alphabet that each box contains. Sort the mathematicians alphabetically, then enumerate them as 1-100. Mathematicians 1 will then rotates boxes 1-50 such that if the name is for mathematicain 1-25, he leaves the box undisturbed, if it conatains the name/number of mathematician 26-50, rotate 90 deg (clockwise say), if the name is for mathematicain 51-75, rotate 180 deg and if it’s for mathematician 76-100, rotate 90 deg anticlockwise.

Mathematician 1 has a 50% chance of opening his box. Mathematician 2 has a 50% chance of his name being in boxes 1-50. If his/her name is in the first 50 boxes, then s/he’ll only have to re-open 6.25 boxes. In the worst case, his/her name isn’t in the first 50 boxes, so s/he’ll go on to open 37.5 (average) previously unopened boxes. The second mathematician will therefore have a pretty high likelihood of finding his/her name. At worst, mathematician 2 will have to re-inspect 24 (if 25 were for his/her group and the first 24 were wrong, the 25th must be his/hers) boxes and then will only be able to open 26 previously unopened boxes. The other extreme is that none of the first 50 boxes are right, so s/he can open the remaining 50. Mathematician 3 will definitely find his/her name and open the remaining boxes. The rest only have to check a maximum of 25 boxes.

I can’t be bothered to work out the probabilities though.

Could do better if take advantage of the boxes having six sides.

16. 16. Chris Said：

I’m a nit. If mathematician 1 finds mathematician 2’s name, then e.g. leave that box unrotated. Then rotate 90/180/270 according to the alphabet for the rest of the boxes. Then mathematician 2 can open the other 50 boxes. Everyone else only needs to open 33 boxes at worst.

If mathematician 2 has to open his box then my last post had a minor error, but the extra (100th) box isn’t a problem, mathematician 3 can open that with plenty of spare. Now mathematician 2 is guaranteed to find his name (as are all the others). The probability of dying is then 50% exactly – and that’s all down to the first mathematician.

Of course, if you aren’t allowed to rotate the boxes, I’m not Chris.

17. 17. Chris Said：

I’m a nit again. There is a 50% chance that mathematician 1 will find his/her name in boxes 1-50. But M1 will definitely know if M2’s name was in the first 50 boxes.

So M1 only has to indicate to M2 that M2’s name is in the first 50 boxes (or not). Timing, winking, slamming the door to the hut or any binary hint will do. The “true” signal is always to be for the next mathematician’s name is in 1-50. Each mathematician simply indicates to the next mathematician wheter (or not) their name is in the first 50 boxes.

Again, the probability of survival is 50% and that is down to the first mathematician.

18. 18. SP Said：

Yep I was thinking along the lines of your last post Chris. Just know the next guy’s name and if it’s also in the first 50, wait 10 minutes before exiting. If not, exit quickly. If the first guy makes it out alive (50/50 chance), you win.

19. 19. here you go Said：

if each person only leaves there box open before they leave the others will know that those boxes are takin

20. 20. Karys Said：

lol
I was expecting a purely logical answer as opposed to the purely practical answers you give ^^
The answer I was expecting has to do with permutations.

21. 21. Chris Said：

Hi Karys. If absolutely no communication (including time tricks) is allowed, there is no need to look at permutations – each mathematician has a 50% chance of finding his/her name. The probability of them getting the chop is 1 – (1/2)^100 ≈ 0.99999999999999999999999999999921

22. 22. Chris Said：

Karys. To edit the problems you have to become an author (I know, you already think you are one). Email Rajesh Lal, connectrajesh {AT} hotmail.com, he can elevate you to an author.

23. 23. Karys Said：

Okay thanks, I’ll ask him someday

Actually I was only given the idea behind one solution, so I’ll have to check it before telling you (I agree with you that it seems quite impossible…) ; it should give a chance greater than 50% for each participant, or it could be wrong.

24. 24. Chris Said：

Hi Karys. Unless there’s some way for the mathematicians to communicate (by any means), anyone who says they can improve on their almost certain doom, is wrong.

25. 25. slavy Said：

Hi, Chris. You are wrong here and this is one of the beauties of mathematics. As I said before there is a unique (up to permutations) strategy that keeps the surviving chances positive, no matter how many people are involved. And yes, there is no communication among the mathematicians. In fact, after their turn everybody goes to a different room and has no contact with the rest…

26. 26. Chris Said：

Hi slavy. I can’t imagine how to do it. There has to be something missing in the problem.

I assume that the mathematicians must close the boxes after examining them. If that’s wrong, then a means of communication does exist, snd then I can propose a 50% (I think) survival strategy.

But other than that, I give up; as has, I suspect, everyone else.

27. 27. Chris Said：

Missing info in the problem: Must the mathematician stop opening the boxes as soon as s/he has found his/her name? Can/must the mathematicians close any boxes that they have opened? Can they leave any items behind (I guess not)?

28. 28. Chris Smith Said：

The first one leaves his boxes open so the next can look in them first before opening the remaining 50 if required.

29. 29. Chris Smith Said：

Finger trouble? My earlier reply doeesn’t seem to be here. First one opens 50 boxes and leaves them open. Second one will find his name if he reads open boxes or it will be in the remaining 50.

30. 30. Antn'y Said：

Would I be right in saying the problem is the same as if after discussing a commong stragetgy each of the 100 mathematicians is sent to 1 of 100 identical rooms at the same time, where each must draw his or her name in order for the group to survive? There is no way of communicating in the rooms, and no way in which time taken ina rooom can offer any information. Essentially we need to improve upon the Wozard of Oz’s thinking.

31. 31. Karys Said：

As soon as one mathematician has found his name he has finished his “turn” so no more box opening.
The boxes have to/will be closed, there really isn’t any communication involved.

32. 32. ryan Said：

easy MAXIMUM 50 so each open ZERO 00
\/

33. 33. ryan Said：

to survive!!!!!!!!!!!!

34. 34. John24 Said：

Ok my timing scheme won’t work since they are now exiting into a separate room.

Since they can devise a strategy prior to entering then it is this strategy which will somehow increase their odds of success. Some sort of selecting boxes method.

Even if I know M1 is in the first 50 boxes that won’t reduce the odds for M2 unless he knows M1s box. This goes the same for each following M, he must know the names and boxes of the previous Ms.

So how can each M know the box number for the previous Ms? I give up.

By the way, what if my timing solution had a period of 2 years instead of 1 minute? The earliest all would die is 100 years after they start. Surely they must know the mathematical odds that any of them will age another 100 years is very small given that they are probably adults already and no sane person would include children in this deadly game!

This only means they will surely die and will have lived a pointless life because they have been a prisoner to this game. At least the sick person who devised this game will also be dead will lessen the pain.

35. 35. Karys Said：

I’ve finally checked the strategy I’ve been given, and it works !
Theoretically it gives a probability of winning of 98%, I remind you that no communication whatsoever is involved in the game, each time you only have to consider one mathematician alone with 100 boxes with 100 names in it (and he may know the names in advance because they can talk to each other before the beginning of the game)… I’ve simulated it (100000 games), but the new room generator may not give exact equiprobability between different games, so I get a 98.88% wins.

Or maybe my proof of the 98% is not fully right, but the simulation seems convincing enough…

I’ll post the answer within this week.

36. 36. Chris Said：

Hi Karys. There must be something we’ve not been told. If there is absolutely no communication of any form whatsoever, no matter how subtle or indirect, I cannot see how any of the mathematicians have a better than 50% chance of finding their names. Obviously I cannot see how any strategy can be devised. I assume that this isn’t a trick question – i.e. the mathematicinas don’t agree to rename themselves, can’t fit glass windows to the boxes, etc.

37. 37. Wizard of Oz Said：

Somewhere between my answer of 9.9 x 10^-30 (post 9) and Karys’s solution of 9.9 x 10^-1 lies the truth.

I’m assuming no communication between the mathematicians after the first one goes in, and that the boxes and the room they’re in are not altered in any way. Each mathematician sees exactly what the others see and can’t see what the previous ones do.

If any mathematician can pick a winning box out of 100 in no more than 50 attempts then I want him/her to pick the numbers for my next lotto ticket.

I look forward to Karys’s solution.

38. 38. Karys Said：

I believe I’ve given all that’s necessary to solve the problem.
I thank Antn’y for the idea of 100 separate rooms.
BTW I have contacted Rajesh Lal, and he replied he elevated me to author, but I have not seen where to edit my posts.

So what these mathematicians have to do is to give each of their names a number between 1 and 100.
Now you could say that one name is in fact a number, you have mathematician 1, 2,… 100.

Mathematician number N is to open box number N. In that box he will find a name, that is a number M. If M=N, then he has finished. If not, then he opens box number M. He will find a number M’, if M’ is not equal to N, then he opens box number M’ etc, each time opening the box the number of which is associated with the name contained in the previous box.

How can this give you a better chance at survival ?

You have to realize that replacing names with numbers let’s you define a permutation of integers from 1 to 100, that is a bijective function from [1,100] (integer set) to itself (refer to wikipedia if you do not know of this notion) :
Let S be that permutation, S(1) will be the number contained in box 1, S(2) the one in box 2…

Then we can “factorize” this permutation into cycles. Let me explain it more clearly :
Let N be an integer in [1,100], then apply S : you obtain an integer S(1) in [1,100], repeat, S(S(1))=S^2(1) in [1,100], etc… if you repeat this a big enough number of times you are sure to come back on 1.
(Proof : repeat this 100 times, you get 101 numbers 1, S(1),…,S^100(1) in [1,100], then there are two equal
S^k(1) = S^m(1) with m not equal to k, suppose k<m
since S is bijective, you can apply its inverse k times, you get :
S^(m-k) (1) = 1, QED.)

So what we are doing with that strategy above is that we are going through the cycle containing number N. After a number of opened boxes, Mathematician N should end with having to open box number N, which is already opened, but let's go back a step : having to open box number N means you have just opened the box containing number N, that is the box you were looking for ! Now with this technique, all you have to hope for is that the corresponding permutation has no cycle of length 51 or more.

Then I let you continue on …
in fact I noticed I may have made a little mistake on the number of permutation having a 51-or-bigger-cycle … what a nitwit I am.

39. 39. Chris Said：

You should then get a “Dashboard” page. I always click on the “View All” button. After that, I just stumble around. I always check the Pending, Spam and Trash and decide what to do. Most stuff under spam usually really is spam. I delete everything that is spam. You can only do that for your own blogs.

I will now see what you have written.

40. 40. John24 Said：

Karys

I suppose that could improve their odds a little, which is all you asked for.

It seems just as logical to start with the box equal to your rank among the 100 Mathematician’s and open the next 49. As long as you put the 100 Mathematician’s in a correct enough order they should survive.

Your solution appears to have the same chance of success. 50-50 for each of the 100.

41. 41. Chris Said：

OK let’s look at a simpler version of the problem with four mathematicians and four boxes. I’ll list the contents of the boxes in box number order (i.e. 1234). There are 24 equally likely permutations of the contents:
1234,1243,1324,1342,1423,1432
2134,2143,2314,2341,2413,2431
3124,3142,3214,3241,3412,3421
4123,4132,4213,4231,4312,4321

Use S/F for success/fail.
For M1: SSSSSS,SSFFFF,FFSFSF,FFFSFS that’s 12S/12F
For M2: SSSFFS,SSFFFF,FFSSSF,FFSSFS that’s 12S/12F
For M3: SSSFFS,SSFFFS,FFSFSF,FSFSFS that’s 12S/12F.
For M4: SSSFFS,SSSFFF,SFSFSF,FFFSFS that’s 12S/12F

So, unless some magic happens by going to more than four boxes, I say that the strategy is useless. They still have a 50% chance at finding their own name.

42. 42. Chris Said：

I hadn’t analysed correctly. For a given permutation, we must look at the S/F for each mathematician. We only have an overall success if they all succeed.
I’ve reproduced the results from my previous teo posts. I’ve added a summary line. It contains an S if all the mathematicians got an S.
SSSSSS,SSFFFF,FFSFSF,FFSFSF
SSSFFS,SSFFFF,FFSSSF,FFSSFS
SSSFFS,SSFFFS,FFSFSF,FSFSFS
SSSFFS,SSSFFF,SFSFSF,FFFSFS

SSSFFS,SSFFFF,FFFFFF,FFFFF => 6/24 = 25%.

I’d expect (1/2)^4 = 0.0625 = 6.25%.

So the strategy does help. I’m flabbergasted.

43. 43. Chris Said：

Sanity check (partial). M1 still only has a 50% chance of success. But if he succeeds, then the probability that the M2 will succeed has gone up.

SSSSSS,SSFFFF,FFSFSF,FFSFSF M1 => 1/2
SSSFFS,SSFFFF,FFSSSF,FFSSFS M2 => 1/2

SSSFFS,SSxxxx,xxSxSx,xxSxFx M2 given M1 => 9/12 => 3/4
SSSFFS,SSFFFF,FFSFSF,FFSFFF => 9/24 = 3/4 (overall)

I assume that in the limit that the numbers of boxes/mathematicians → ∞, that the overall probability → ½ (or some other, no doubt, important mathematical constant).

I’m still flabbergasted.

44. 44. Karys Said：

Surprising isn’t it ? ^^
So it seems like my simulation was not right…

It’s an interesting comment you’ve made, that the 1st mathematician succeeding increases the next ones chances of success.

45. 45. Chris Said：

I’ve thought about these chains enough to know that the equations to fully describe the problem are probably going to be quite tedious to derive and use. Even the relatively simple problem of finding the number of possible chains of length k with n boxes doesn’t look too easy. e.g. start by saying that we want the chain to include box 1 and the chain length is to be k. Box 1 can point at any of n-1 boxes. That 2nd box can point at any of n-2 boxes. That 3rd box can point to any of n-3 boxes, … through to the k-1 th box which can point to any of n-(k-1) boxes, but the k th box must point to box 1. Altogether that’s (n-1)(n-2)…(n-(k-1)) = (n-1)! / (n-(k-2))! possible chains of length k that include a particular box (LOL, I wouldn’t be slightly surprised if I’ve goofed that). I’ve not ensured that none of those intermediate boxes short circuit the chain. As to finding a probability, LOL, not in less than a few days at best after eating loads of brain food. So I’m going to stop there.

Thanks for the problem Karys – definitely a good one. It certainly caught me out.

46. 46. Chris Said：

Hi Karys. With numbers like 100! ≈ 10^158 permutations, simulating it might be rather tricky (but perhaps Monte Carlo is a more powerful technique than I give it credit for).

“The 1st mathematician succeeding increases the next ones chances of success” – now you put it like that, it does seem bizarre in the cold light of day I had realised it in a sudden and temporary insight just as I started writing the comment, and before doing the check.

OTOH, if M1 fails, we get:
SSSSSS,SSFFFF,FFSFSF,FFSFSF M1 => 1/2
SSSFFS,SSFFFF,FFSSSF,FFSSFS M2 => 1/2
xxxxxx,xxFFFF,FFxSxF,FFxSxS => M2 S given M1 F = 3/12 = 1/4.

So M2 is also more likely to fail if M1 fails. I think that I reckoned that it is more likely that a given pair of mathematicians will be more likely to be in different chains (rather than in the same chain) as there are likely to be lots of chains. I haven’t directly checked that; but the results seem to be consistent with that idea.

47. 47. Chris Said：

Having re-read my last comment, my brain has melted. Cognitive dissonance rules again.

48. 48. Chris Said：

… sorted, I really meant that I think that they were more likely to be in the same chain – but I can’t remember how I reasoned that

49. 49. slavy Said：

Hi Chris,

yeah, as I said before, the problem is very beautiful and to some extend even counter-intuitive First of all, dealing with small n is not a good approach, since here we are looking for the asymptotic behavior when n tends to infinity. It is the same as with throwing a dice – we know that we expect a number very close to 3.5 to be the average of all the throws, but if you try to simulate it for up to 10 throws you will not believe it…

The beauty in this construction is as you said, when losing (i.e., not able to survive) the mathematicians do it badly. Indeed, if one dies, it means that we have a cycle of length at least 51, so (if we switch to the version with simultaneous opening of the box in different rooms by all the people) more than half of the people should fail and they all should be the reason for the rest to die. Thus, kn some sense, we group a lot of bad individual outcomes into a single one group failure, which tremendously increases the overall success I am not sure if you got me, but I wrote this in a hurry, and haven’t read it myself…

50. 50. Chris Said：

Hi slavy. I had no choice but to deal with a small n, To mimic the problem better I would have liked to have used 6 boxes and mathematicians. Then I would have had 6! = 720 permutations, that’d involve a lot of effort.

I agree, it is a beautiful result – I never would have guessed it. I at least realise, that every box is in a chain. There could be 1 chain of length 100 (but 99!/2! ?? different possibilities for it), through to 100 chains of length 1 and very very many mixtures of chains of every length in between those extremes.

51. 51. slavy Said：

Hi Chris, I apologize for not speaking with formulas here, but I know the problem is not easy to compute and I really don’t have the time to do it right now, so I am just waving some heuristic arguments. Let us just compute the probability that the group fails. In this case it means that at least one of the mathematicians didn’t find his box. But since everything is independent of the order (again, I use the version with the 100 rooms and simultaneous openings) let us always denote by MATH the mathematician with the worst luck, i.e., the one that needs to open the most number of boxes until he finds his own. Note that, due to the procedure they are doing, this guy is not unique – they are as many as the number of boxes they have to open. The probability that MATH is not able to find his name in 50 trials is something like (99/100)*(98/99)*…*(50/51)=1/2 (we just multiplied the chances that at each of his first 50 trials he fails). But, once he failed we already have the complete picture for all of the others! Indeed, all the numbers, opened by MATH will have the same destiny as his own, while the remaining less than 50 people are part of one or many other cycles, that have nothing to do with this one, and thus they will all surely find their names within the 50 attempts. Therefore, the probability that they all will fail is the same as the probability that MATH will fail. Since MATH is a single person, the logic tells us that the latter should be exactly 1/2… Of course, I am not sure in the answer right now, because I didn’t provide enough mathematical arguments in the post, but at least it explains why the chances of the mathematicians are far beyond (1/2)^100…

52. 52. Chris Said：

Hi slavy. No problem, I was pretty sure that all the formulas are going to be pretty evil.

I might commit blasphemy and try a computer simulation, even if it’s only to demonstrate a nice way to randomly distribute the names into the boxes. It also can be used to shuffle cards.

53. 53. Chris Said：

I’ve blasphemed and written some code. Preliminary results suggest that the mathematicians have about a 30% chance of survival. That’s vastly better than the 7.89*10^-29 % (i.e. almost certain doom) that random selection would have given them.

I also played with the number of picks. From about 80 picks and up the probability of success gets close to #picks/100%. I conjecture that all of that lies with the first mathematician, and that if he succeeds, the others are almost certain to succeed s well.

I’ll double check my code, and possibly add some chain counting stuff to it (if I can do that without mucking the whole thing up) and publish a link to it. It’s in Excel VBA and so should also be compatible with VB6.

54. 54. Ryan Said：

well. in the problem it doesnt say the mathmaticians had to close the boxes when they are finished. so if the first guy gets lucky and finds his name in one of the boxes, the next guy can go in. look in the already opened boxes, and open 49 more boxes to help. then the 3rd guy will go in and have almsot all the boxes open and will just peer inside and find his name and open the remaing boxes for the rest of the people.

55. 55. Euclid's Brother Said：

I am quite amazed. I wrote a program to test this as well and can confirm Chris’ results.

I ran my sim 40 times and got these results:
17/50 = 34% Survival rate
33/50 = 66% Death rate

Of the Deaths,

23/33 failed on first person = 69.6969%
5/33 failed on second person = 15.1515%
2/33 failed on third person = 6.0606%
3/33 failed on fourth person = 9.0909%
No failurs after fouth person.

56. 56. Euclid's Brother Said：

hmm.. those results was running the program 40 times, but when i put a loop around the whole thing so i can run over and over in one run, then i’m getting a near about 97% death rate.

on 100,000 loops, i get 96.232% death rate.

57. 57. Chris Said：

Hi EB. I ran the test many times, each run was with 10 000 trials. I get about 29.8%.

I want to add those other intermediate statistics too.

I’ve had to recover Windows during the night (my PC wouldn’t start) so it’ll be a while before I can post the code.

Hi Karys. I just want to say thank you for posting the problem. I can safely say that it is the most counter-intuitive and paradoxical probability problem that I have ever seen. The result is quite stunning. And for the icing on the cake, you’ve caused me to become aware of the chains in the permutation (groups??).

58. 58. Chris Said：

Hi EB. I suspect you’ve got some debugging to do. I’ll put my code (as is) up in about half an hour. That’ll be via a public link to Google Blogs. I’ll update it later.

59. 59. Euclid's Brother Said：

hmm.. perhaps that test above was prone to a random number generator pattern. I’m using C#.NET and was creating a new random number generater in each loop, which should be well enough.. in my previous test, each run would be with a newing created randome number generater.

I did another test where I create a single randome number generater and just keep getting new random numbers off of it throught all loops.

Death rate on 1000 loops was 67.4%. And each successful person does indeed increase the chances for the next person.
[Person 1]: 501 Fails
[Person 2]: 105 Fails
[Person 3]: 39 Fails
[Person 4]: 11 Fails
[Person 5]: 5 Fails
[Person 6]: 8 Fails
[Person 7]: 1 Fails
[Person 8]: 1 Fails
[Person 9+]: 0 Fails

I’m gonna run it over a million loops and report back in a few hours.

60. 60. Euclid's Brother Said：

Here’s my source code:

http://snipt.org/wppmp

61. 61. Chris Said：
62. 62. Euclid's Brother Said：

In Chris’ own words “I’m a nit”.

I didn’t consider looping chains, which would account for my slightly higher death rate. I’ll work on it some more later.

63. 63. Chris Said：

Hi EB. You don’t seem to have checked for a previously opened box, i.e. you haven’t dealt with a small chain; that’s why you’re killing them off too quickly.

10 000 loops should get you to 1% of the probability (i.e. +/- 0.3%. 1 000 000 will improve that to +/- 0.03%, where I’ve aasumed success as 30%.

Sadly, I’m not familiar with C#, but I do like that contains method, albeit a bit of an expensive way of loading the array.

Take a look at the technique I used. I’ve not used it before, but remembered the idea from a long time ago. It was used for shuffling cards. It’s pretty efficient. e.g. if we had a few million boxes, your method could take a very long time (hours perhaps).

Thanks for the code though. I might fire up a copy of Visual Studio and play with it. But only after tarting up and extending my VB (Excel) code.

64. 64. Chris Said：

Hi EB. LOL. Posts crossed. You’ve nicked my catchphrase

65. 65. Chris Said：

I’ve updated and tidied up my code a little.

66. 66. Wizard of Oz Said：

Hi Chris,

All this is certainly counter-intuitive, and I don’t understand a bit of it!

For the benefit of dullards like myself could you explain (in simple terms please) just what is the strategy that the mathematicians agree on before the first one enters the room, and why the survival of the first one should so greatly improve the chances of the rest of them. I have no idea what looped chains are.

Have the rules changed from the initial statement of the problem?

My next suggestion was going to be that the mathematicians attempt a mass breakout – their chances might be better than 10^-30 or whatever.

67. 67. slavy Said：

Hi Wiz,

let me try to explain a little what goes on here. First of all, I hope it is clear that the problem can be reformulated in the following way: Taking a random permutation P=(P(1),P(2),…,P(100)) of the numbers between 1 and 100, find the optimal strategy so that for all 0<i<101 the i-th mathematician gets to his box (which is P(i) in our notation) in less than 51 trials with the highest possible probability.

Now the trick is how to "visualize" a permutation. Usually the permutations are writen just as a sequence, e.g., 531246 of its elements. However, this does not give us the information we need, so it is better to write the same permutation as P={342516} which is already in line with the notation (P(1),P(2),…,P(6)) and tells us that 1 has been moved to position 3, 2 has been moved to position 4, 3 has been moved to position 2, 4 has been moved to position 5, 5 has been moved to position 1, and 6 has not been moved (i.e., it stays in position 6). Now at least we know which box each of the mathematician needs to open (e.g., the first one has to open #3 and so on). But if you open any textbook on linear algebra and look for permutations, group of symmetries, etc., you will see that the classical approach (which actually is used in verifying all the results) is to write the permutation in terms of cycles (or loops, as some of you call it, even though it is not mathematically correct). Particularly, we can write each permutation as a unique collection of disjoint cycles (as Karys even proved somewhere above), e.g., P1=(13245). When the cycle consists of a single element usually we don't indicate it at all in the formula. Let me explain how I derived the last formula. I started with the second representation P={342516} and build the cycles one by one. The first cycle should always contain 1. We look at P and we see that in the first place of P is 3, so we write 3 after 1, obtaining 13. Now we see that in the third position of P is the number 2, and we add it to our cycle – 132. And so on. The cycle ends when we reach 1. Note that it is impossible to reach twice any other of the elements in the cycle before hitting 1, and this is why it is called a cycle. In our particular case we see that the cycle, that contains 1 is (13245) and only 6 is left outside. We just verify that 6 forms its own cycle (6 is already at position 6, so we hit it immediately) and end up with the permutation P1. The good thing here is that, by construction, we are sure that i and P(i) are always in the same cycle, so there is no point for the i-th mathematician to look for his box outside of his cycle. And this is the beauty of the problem! Each mathematician will have to open as many boxes as elements there are in his cycle, and since the cycles are disjoint there is no chance to have more than one cycle of length larger than 50 in a permutation of 100 elements, meaning that if one mathematician fails to find his box within the first 50 trials, we already know who else will fail (all the people from his own cycle) and who will succeed (all the people from the other cycles). And this is what we mean by: "the failure of one completely determines the group picture"…

P.S. I am always sloppy with this things, so again somewhere in the explanations I switched to the inverse permutation of P and the actual order of opening the boxes is from right to left in each cycle, e.g., following the strategy mathematician 1 will open the boxes in order 54231, since the cycle was 13245, while mathematician 4 will open the boxes in order 23154 and so on…

68. 68. Chris Said：

Hi Karl. You aren’t a nit, I am. There is no need to mark the boxes as having been opened. I have just chopped a load of stuff from my code. http://trickofmind.com/wp-content/uploads/2011/10/100-mathematicians.txt

Every box MUST be in a chain (cycle), but its significance eluded me). The only variable is the chain length. If any chain is longer than 50, then they’re doomed. If all the chains are less than 50 then they are going to be OK.

Of course it may be the the first mathematician is in a small chain, but that doesn’t guarantee that e.g. the second one isn’t in a chain of length of length greater than 50.

It must be that the probability of having no chain larger than 50 is about 30% (in the posted problem). I feel fairly (surprisingly) comfortable with that idea and magnitude. Put another way, the probability of having a chain of length greater than 50 is about 70%.

I shall probably write a program to find the probability distribution of chain lengths.

Hi Wiz. In case you haven’t got it yet. A chain (cycle) is when e.g. box 1 points at box 2, and box 2 points at box 1. That would be a chain of length 2. If box 1 pointed at box 1, the chain would be of length 1. But no matter what, every box must be in a chain; in the worst case the length is 100 – that is inevitable.

It cannot be that a box points at another box etc., without one of them eventually pointing back at the initial box. You must go round a loop (or chain or cycle, as you prefer).

69. 69. Wizard of Oz Said：

Hi Slavy and Chris,

All that I can see that you have done is give the first mathematician (M1) an algorithm for selecting her (up to) 50 boxes. Instead of choosing boxes 1-50 as I have suggested she chooses the box number corresponding to her M number, 1 in this case. Then whatever M number is in box 1 leads her to the next number in the so-called “chain”. To me this is just another way of picking (up to) 50 numbers, with no more guarantee of success than if he had gone from boxes 1 to 50, with probability 50%.

Now tell me, how does M2 have any greater chance of success than 50%? I assume that M1 has not left him a little note to say that she found the box corresponding to M2 while looking for M1. I’m also assuming that the boxes, once opened, are closed again or, if you like, the 100 mathematicians open their 100 boxes in 100 different rooms. So M2’s chances of success, starting with box 2, will be exactly the same as M1’s, namely 50%.

Likewise with M3, M4, etc, up to M100, all of whom will surely die with probability 10^30 or thereabouts.

So what am I missing?

70. 70. DP Said：

Well…if this one is going to knock my problem off the top 5, I might as well be the one to help it get there. This post should even them up, and so the next will certainly put it in the top 5 popular posts.
Congrats Karys!

71. 71. slavy Said：

Hi Wiz,

you are missing that the cycles are disjoint, that every mathematician checks only his own cycle, and that with the number of elements increasing, the probability that a random permutation has a cycle, that contains more than half of the elements decreases. Opening boxes at random makes every mathematician’s strategy group-independent, while in this setting the search is very well-structured and depends not on all the individuals but just on few of them (we need to take a single representative from each cycle! All the rest in the cycle have identical outcome). Moreover, in this restricted setting only one of the chosen mathematicians may fail, leading to overall probability between 1/2 (the probability that a single people, opening boxes at random survives) and 1/4 (the probability that two people opening boxes at random and independently will survive).

72. 72. Chris Said：

Hi Wiz. The mathematicians really don’t communicate with each other or leave any boxes open – fair dinkum. The chained boxes strategy really does the job.

You are right, each mathematician still has a 50% chance of failing to find their name. But that doesn’t mean that they have a 50% probability independently of each other.

Chains of length 1 through 100 are possible. Typically there will be quite a few different length chains. I suspect that a length near to 50 is quite common (it may even be the most probable length). I’m almost certain that a chain of length > 50 occurs approx 70% of the time.

For a given chain, of length L, it doesn’t matter where you start in it, you will have to open L boxes to go round it. If M1 happens to be in a chain of length L, then so do L-1 other mathematicians. So all L of them either find their names or don’t – hence the non-independent probability for each of the L mathematicians). Of course we don’t know which of the mathematicians are in the chain, only that L of them are.

If no chain is longer than 50 (which I believe happens approx 30% of the time), then every mathematician will find their name as every chain is less than 50 long.

At most, there can only be one chain of length, L > 50. If there is such a chain, then any other chain(s) must be shorter than 50, and all 100-L mathematicians in those shorter chains will find their name.

73. 73. Chris Said：

Hi Wiz. I’m really writing this to get the popularity up. I’ll re-state that every box is in a loop (I think that’s a more descriptive word than chain), and that no chain includes another (as slavy says, they are disjoint).

Just write down 10 numbers (say) in random order, then pick one of those numbers and draw a line from it to the number at the position it implies (or you could colour them). Then draw a line from that to whatever position it refers to etc. You will end up with a loop. It’s a bit like playing clock patience. In general, some of the numbers may not be connected. So do the same procedure with one of the unlined numbers. If necessary keep on doing that. Eventually every number has a line through it, but they connect sepearate groups of numbers.

Sorry, that’s not well put.

74. 74. slavy Said：

OK. Obviously, I was wasting much more time when writing vague stuff, instead of computing the actual answer, so let me “close” the topic (at least for me! plus, I appologize to DP that I didn’t do it earlier so that his post might still had been in top 5 ). The computations are actually not dificult, at all. Let us fix the number n, and let m be arbitrary, greater than [n/2]. The probability that we have a cycle of length m in a permutation of n elements is just:

probability of m-cycle= C(n,m)*(m-1)!*(n-m)!

Explanation: First we choose which m numbers will form the cycle. Then we choose the order of those elements in the cycle (since we are dealing with a loop, i.e., permutations on a circle, we have (n-1)! instead of n! different outcomes). Finally, we permute the n-m elements that are not in the cycle. This counting does not work for smaller m’s, because there we may have more than one cycle of order m, and, thus, we count such permutations more than once. Here, however, everything is all right. But

C(n,m)*(m-1)!*(n-m)!=(n!/(m!(n-m)!))*(m-1)!*(n-m)!=n!/m.

Hence, the probability that more than half of the elements are concetrated in a single cycle is just the sum of 1/m for all m, highen than [n/2] and less or equal to n. In case n=2n1 is even, then the probability is

1/(n1+1)+1/(n1+2)+…+1/(2n1)=H(2n1)-H(n1),

where I denoted by H(n) the n-th harmonic sum. For the concrete problem n1=50 and direct computations give the answer H(100)-H(50)=0.6882…=69% Therefore Chris simulated the problem very well In general, due to Euler, we have that, as n tends to infinity, the difference tends to ln2=0.6993…=70%, (see http://en.wikipedia.org/wiki/Euler_constant ) from below, i.e., the death rate doesnot exceed ln2 and for all big enough n mathematicians we have at least 30% chance that the whole group survives… My advisor will kill me for my “scientific work” today
H(100)-H(50) ≈0.68817218. So P(surviving) ≈ 0.31182782

75. 75. Chris Said：

Hi slavy. Thank you. I hadn’t realised that the calculation for a > n/2 chain would be so simple . When I tried to do it, I started with a loop of length 1, and my head quickly exploded after that.

Now you’ve done that, I agree that, sadly, the problem seems to have run it’s course. It almost seems dull now (LOL).

At least I was right in that ln2 is an important number but perhaps more to a physicist than a mathematician.

NB don’t put ()’s round links, WordPress thinks the ) is part of the link. I’ve added a space char to fix it.

76. 76. Wizard of Oz Said：

Ah, now I see it. Closed loops within sets of consecutive numbers 1 to n. I hadn’t come across this before. A most interesting phenomenon, and self-evident now that it’s pointed out to me.

Thank you Slavy and Chris for your patience in explaining this to me, and thank you Karys for a most interesting puzzle.

77. 77. Chris Said：

Hi Wiz. Even though I’d understood the loops (and like you hadn’t come across them before), the whole penny hadn’t dropped – hence my originsl code had lots of unecessary stuff. For some reason I thought that if the mathematician got back to his start box, he may not have found his name – DUUHHHH!!!! of course he must have found his name (LOL). When I got over the shame and embarassment, it all fell into place.

Hi EB. I’ve run your code (briefly). But I can’t see anything wrong with it. Are you sure that you’re interpreting the results correctly? They seem fine to me.

78. 78. Chris Said：

I’ve done a chain analyser proggy. Despite slavy’s (obviously correct) observation that his analysis is only valid for chains > n/2, in practice, the probability of having two small chains of the same length is so small that a pretty good approximation is that the probability of having a chain of length m is 1/m (independently of the size number of boxes). I have only tested this with 100 boxes (so far). I really mean that on average I got (a tad over) one chain of length 1. Based on 1,000,000 trials I got 1,002,315 chains of length 1. I don’t have better information than that.

For that run, the error from theoretical for the probability of a chain of length > 50 was 0.017%.

79. 79. Wizard of Oz Said：

Hi Chris,

I suppose that this is another way of saying that if 100 mathematicians open 100 boxes with each of their names in them, then there is a more or less even chance that one of them will find her name first up. This sounds about right.

80. 80. Chris Said：

Hi Wiz. That was ambiguous . I hope the next isn’t. If any one mathematician opened 50 boxes either using the strategy or randomly, there’s a 50% chance that he’d find his name. That applies to all of them; so there is no need to re-adjust our models of reality.

But with the strategy, then all the mathematicians that share a loop will all succeed or fail together. Also, if they succeed, they may not have to open as many as 50 boxes.

Of course the probability of a mathematician being in a loop = length of loop/100. The full analysis is slightly tedious (a euphamism for I can’t be bothered to do it ), but not hard. In the end, the only thing that matters is that the logest loop length is < 51.

Because I had stated the probability of a loop of length 1 is 1 (which obviously is nonsense), I'm about to tweak my loop analysis program to get more info on that. I knew when I wrote my last post that sometimes you'll get 0 of length 1, mostly 1 such loops and more rarely 2, and more and more rarely 3,4,5,…,100. I expect that the average will turn out to be quite close to 1. I suspect that the probability of getting 2 or more is balanced by the probability of getting 0 (loops of length 1).

81. 81. Chris Said：

Here’s my loop statistics proggy: http://trickofmind.com/wp-content/uploads/2011/10/100-mathematicians.txt

There’s too much data to describe it all, but based on a million trials I get (number of loops, occurrences):
Length 1: 0,368849; 1,367377; 2,183878; 3,60978;
4,15315; 5,3003; 6,520; 7,70; 8,9; 9,1; 10,0

Length 2: 0, 607071; 1, 302609; 2, 75871; 3,12671; 4,1585; 5,178; 6,14;7,1
Length 3: 0,717624; 1,23767; 2,39838; 3, 4494; 4,359; 5,21

Length 32: 0, 969439; 1,30094; 2,465; 3,2
Length 33: 0,970112; 1,29443; 3,0 (that was a surprise)

Length 50: 0, 980230; 1,19557; 2,213
Length 51: 0, 980554; 1,19446

Length 99: 0,990133; 1,9867
Length 100: 0,990133; 1,9867

Try not to fall asleep reading that.

So that probability 1 for a loop of 1 is only a pseudo-probability.

82. 82. Chris Said：

Oops. I goofed the length 99 and 100 stats. I had to do another run (which also gave 0 occasions with 3 loops of 33).

Length 32: 0,969389; 1,30132; 2,473; 3,6 (so that was a fair bit different).

Length 99: 0,989680; 1,10320
Length 100: 0,990151; 1,9849

Yawn.

83. 83. Wizard of Oz Said：

Hi Chris,

Interesting. Did you get figures for the average number of loops for 100 boxes? Is there much variation? Just idle questions – don’t go to any more trouble if you didn’t get these.

84. 84. Chris Said：

Hi WIz. I’ve tweaked the code posted code. 5.18 loops on average Thanks for asking, I should have thought of that statistic for myself.

85. 85. Chris Said：

Hi EB. I haven’t been careful with the use of the Randomize function. It uses the system clock as a seed. If a very small period of time has elapsed between the calls, the same sequence would be generated. Randomize should be called once at the start of the program and never called again.

86. 86. Elías Said：

Hey everyone.

I have an idea of how their chances of survival could increase.
Now, we all know that when M1 goes in they have a 50% chance of survival no matter what they do. Let’s say he got it right. Now he cannot leave any clue which box he got right but there is a system everyone can use to organize the boxes before going in. That is, every mathematician agrees on what box is #1, #2 and etc….
The system works like this: When M1 goes in, he will open box #1 in exactly 1 minute. If he is unsuccessful there, he will open #2. This will go on and on until he reaches box #50 unless he gets it right. If he opens box #50 and he doesn’t get his name, everyone dies and there’s no point on going further, duh. But if he get’s it right somewhere within those 50 minutes, he will go back outside in exactly 1 minute. Now he can’t give any of the other mathematicians any information but they now have an idea of what box they should not open.

So if M1 got his name on B1, he will be out in 2 minutes.
B2:3 min, B3:4 min….. B50:51 min.

So the time it takes him to find his name helps the other to find out which box will most certainly not have their name on it. If M1 gets it right, M2 will only have to worry about 99 boxes, and he know’s precisely which of the first 50 boxes he should not choose. This will go on and on for each mathematician. Each time a mathematician is successful, the chances of survival will increase until M50 is done. Then, everyone else is safe.

87. 87. Jack Said：

i dont know if this answer has been given as their are too many to read (my bad)

on a logical basis,
it states that anyone who comes out of the room may not reveal the contents of the boxes. so while in the room the mathematician may make a phone call and reveal the contents or simply write down the name in the box on the outside of the box. as long as the mathematician is still in the room he may reveal the contents

88. 88. Jack Said：

i dont see how this game could have a percent chance that you could win.
for example based on my method above there is still a fifty percent chance that the first person fails and so they all die.

there must be another trick to it, as a riddle like this would involve using specific words so that you see a solution where this is guaranteed success.

based on that theory i notice that the riddle does not say how many times a person may enter the room only that a person may only open 50 boxes.
so if the first person goes in and opens 49 boxes or until he finds his name and he writes down on the box the names that are within the boxes. then he leaves and the second person enters and opens 49 boxes or until he finds his name.
when all the boxes have been opened then anyone who has not yet found their name simply needs to go in and find it.

89. 89. Chris Said：

Hi Jack. Just read posts 38 and 74. The probability of survival is a tad over 30%.

90. 90. rabecca Said：

Yes everyone look in each box and flip your name over if they have already found it. So the answer would have to be yes.

91. 91. rabecca Said：

92. 92. Trevor Said：

First mathematician go in and open the maximum number of boxes (50) take their name out, leave the boxes open, then the rest of the mathematiccians go in until one finds his name isn’t in the first 50 opened, so he now opens the next 50, and the flow continues until all names are claimed.

93. 93. Real Not probability Said：

It says that no one out of 100 mathematicians knows where their names are. And it says that no one AMONG the MATHEMATICIANS must give information about the boxes they open. So, ask other person that is not a contestant to look at the boxes where their names are then they already know where to find their names!
BTW: other answers are giving only the chances, the real question is to find out what is the strategy, not the probability (no offend)

94. 94. xXxVatchXxX Said：

could the formula Y=(X+2)/(4X) work where X is the number of people and Y is the probability of success? It works for 2,3,4,5,…

when every time the number of people is odd and don’t have an integer value of available picks, it is counted as the previous Y value for some mystical reason

ex. when the number of boxes is 5, and the person finds their name in 3 tries instead of 2.5, it is counted as 3/8

if this formula is right, then surviving 100 boxes would have a 25.5 percent chance

95. 95. Chris Said：

Hi xXxVatchXxX. I’ve no idea how you came up with that. But it must be wrong because as X → ∞, the probability of them surviving → 1 – ln2 ≈ 0.3068528…, not 0.25.

Hi Real Not probability. The strategy was given in post 38. Post 77 shows what the probability of that strategy working is.

Most of my posts are out of personal interest in what for, I guess most of us, is a new discovery. They are not intended to be an answer to the question.

96. 96. xXxVatchXxX Said：

i knew that the chance of picking from two boxes was .5 and from 4 was .375 so i multiplied 2 by .5 and 4 by .375 which gave me
1 and 1.5 so i made a line out of that (.25X+.5), divided it by x and it looked right.

97. 97. xXxVatchXxX Said：

never mind im retarded

98. 98. Chris Said：

Hi xXxVatchXxX. LOL, I like your attitude.

99. 99. Peter Said：

everyone open box 1 and then someone will find their name

100. 100. Chris Said：

Hi Peter. That guarantees that they will die

101. 101. Peter Said：

Chris it says that if one has NOT found their name they all die but if they all open the same box then one of them will find their name.

102. 102. Chris Said：

Hi Peter. I also misinterpreted it that way at first. See post 3. The phrase means that if any one of them fails to find his/her name, then they all will die. So if only 99 find their name, they all die. With the other interpretation, the problem would be mind-numbingly boring.

It is only with the interpretation that they must all find their own names to survive, that problem has an amazing solution. See posts 38 and 74 to appreciate what an excellent problem this is.

103. 103. Peter Said：

that makes sense to i was thinking on a different line

104. 104. Chris Said：

Hi Peter. Thanks to you and me, this problem has displaced the utterly contemptible “man in the room”. Congrats to Karys

105. 105. DP Said：

It looks like you need some help in KEEPING this one in second place. The “Man in room” is catching up again. Ironically, partially due to you, Chris, in an attempt to stop people from answering it. Funny thing…someone posted right after starting with “Ok, I did not read any other comments…”
Just doing my part…again…since my problem is completely out of the top 5 and not coming back.

106. 106. Chris Said：

Hi DP. …but I’ve deleted some of my earlier posts on “man in a room”, and I’ve just added a post here

107. 107. DP Said：

Isn’t that cheating, since you are the only person other than Rajesh that can edit other’s posts, and you are the main author or problems on here? (at least in my eyes, haven’t checked the stats)

108. 108. Chris Said：

Hi DP. Yep, it’s definitely cheating. But I resisted the temptation to delete the entire blog or anyone else’s post. 108 posts for Karys now.

109. 109. Karys Said：

lol I see this problem has caused some discussion ^^

110. 110. DJ7 Said：

Hi,

According to me the best strategy would be.. each person who enters in and finds his name should keep the box aside so that the next person entering will not waste his chance by opening the same box (there by increasing the probability).. and also there should be a definite order of the mathematicians entering the room. The first person entering should use his chance of opening 50 boxes entirely (even after he has found his name) and try to place the boxes in that order (Because he has already found his name, he will place 49 of them in order). The next person following the first will open the first box among the ordered ones (not the box kept aside but from the first 49)… if he finds his name then he can place it aside and then open boxes from next 50 boxes (which are not ordered) and start inserting into the first set of boxes… if he doesn’t find his name (he might have found someone following his name from the agreed list) then he can directly go to the next 50 (unordered) boxes.

Hope I have conveyed it properly!

111. 111. Chris Said：

Hi DJ7. You are not allowed to move the boxes or leave them open or communicate with any of the other mathematicians in any manner whatsoever. I admit that’s not completely clear in the problem as posted. That was confirmed in posts 7 and 12 (and at least one more).

112. 112. Chris Said：

I’ve updated the source code for this:

113. 113. sanjay Said：

wat r the name of 50 mathmatican
thanks

114. 114. Deedlit Said：

I’d like to make some comments on Chris’s calculations.

He calculates the number of 1-cycles appearing in a million random permutations, and derives a “pseudo-probability” of 1. Since he counts the permutations with more than one 1-cycle more than once, this pseudo-probability is actually the expected number of 1-cycles in a random permutation, rather than a probability of at least one 1-cycle appearing.

In fact the expected number of k-cycles is 1/k for all 1 <= k [n/2], the number of k-cycles can only be 0 or 1, so the expected number of k-cycles is exactly the probability of a k-cycle occurring.

To calculate the probability of a k-cycle occurring for k <= [n/2], you need to use the principle of inclusion-exclusion.

Suppose you have a space of size N, and a collection of events A_1 through A_k. Let N_0 be the number of possibilities in which no events occur, and let N(A_i1, A_i2, … A_im) be the number of events in which A_i1, … A_im all occur. Then the principle of inclusion-exclusion states that

N_0 = N – Sum N(A_i1) + Sum N(A_i1, A_i2) – … + (-1)^k N(A_1, A_2, … A_k)

Let's use P.I.E. to count the probability of a 1-cycle in a random permutation of n letters. Obviously N = n!. Suppose we want to leave k particular 1-cycles fixed. There are (n-k)! permutations that do that. There are C(n, k) ways to choose the k particular 1-cycles, so the kth term in the series is

C(n,k) (n-k)! = (n!/(k!(n-k)!))(n-k)! = n!/k!

So N_0 = N – Sum N(A_i1) + Sum N(A_i1, A_i2) – … + (-1)^n N(A_1, A_2, … A_n)
= n! – n!/1 + n!/2! – n!/3! + … + (-1)^n (n!/n!)
= n! (1 – 1/1! + 2/2! – … +(-1)^n/n!)

So P(zero 1-cycles) = 1 – 1/1! + 1/2! – … + (-1)^n/n!
~ 1/e for large n

P(at least one 1-cycle) = 1/1! – 1/2! + … – (-1)^n/n!
~ 1 – 1/e for large n

For general k, suppose we have chosen m particular subsets of size k to be the k-cycles. The number of ways of permuting each of the m k-subsets to be a k-cycle is (k-1)! and the number of ways of permuting the remaining elements is (n-mk)! So the number of ways is ((k-1)!)^m (n-mk)!.

Now we need to calculate the number of ways of choosing m subsets of size k. One might think this is C(n,k)C(n-k,k)…C(n-(m-1)k,k); however, this chooses the sets in a particular order. To count the number of choices without ordering the m subsets, we must divide by m!

So our final number is

C(n,k)C(n-k,k)…C(n-(m-1)k,k) / m! * ((k-1)!)^m (n-mk)!
= n!/((k!)^m (n-mk)! m!) * ((k-1)!)^m (n-mk)!
= n!/(k^m m!)

So

N_0 = n! – n!/(k 1!) + n!/(k^2 2!) – … + (-1)^n n!/(k^n n!)
= n! (1 – 1/(k 1!) + 1/(k^2 2!) – … + (-1)^n / (k^n n!) )

Prob (zero k-cycles) = 1 – 1/(k 1!) + 1/(k^2 2!) – … + (-1)^n / (k^n n!) ~ e^(-1/k)

Prob (at least one k-cycle) = 1/(k 1!) – 1/(k^2 2!) + … – (-1)^n / (k^n n!) ~ 1 – e^(-1/k)

One can check these against Chris's calculations and they fit quite well.

More generally, the number k-cycles in a random distribution goes to a Poisson distribution with mean 1/k as n goes to infinity. More specifically,

Prob (there are exactly m k-cycles) ~ 1/(k^m e^(1/k) m!)

Again, one can check this against Chris' results, and the numbers match quite well.

I won't prove the Poisson distribution, but heuristically it is quite clear. From a random distribution of n letters where n is very large, we can pick a random cycle and remove it. Say the cycle has m elements. Whether or not m=k, the remaining elements will be a random permutation of n-m elements, which is basically n for n very large. So the probability the next randomly picked cycle is of length k is the same as the first, and the two events are independent. So we end up with a large number of independent events of the same probablity, which leads to a Poisson distribution.

Chris also calcuates the average number of cycles. Since the average number of cycles of length k is 1/k, the average number of all cycles is 1/1 + 1/2 + … + 1/n = H_n ~ log n + gamma ~ log n + .577. For n = 100 you get 5.187, which is quite close to Chris's calculation of 5.18.

Notice that the average length of a cycle is n / H_n ~ n/(log n + gamma). On the other hand, if we choose an element at random, there is a 1/n chance it is in a k-cycle for 1 <= k <= n. So the average orbit of a random element is (1+2+…+n)/n = (n+1)/2.

115. 115. Chris Said：

Hi Deedlit. I’m many months too late, but thank you very much for your post. It is very useful. I’ve made a copy for my library.

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0