Sauron is giving out 100 rings in boxes but this time there is a twist... The names of 100 people (all names are different) are written on 100 boxes each of which has a ring. The 100 boxes are taken to a closed room, randomly shuffled and put down in a row.Each person in turn enters the room and opens the boxes one after another until either he finds the box with his name or he has opened 50 of the 100 boxes. After that he leaves the room, without communicating anything to the others, and the boxes are all closed before the next person comes in.How large can they make the probability that everyone will find the box with his name?The worst is (1/2)^50. If they can make it above 29% they get to keep the rings The people can communicate before distribution of course and decide on a strategy...whats the strategy to maximize the probability!

No you can't change the arrangement of the boxes or rings...and can't take them out!Let's say if names are numbers 1 to 100....then?

If they can move the box I have "maybe" a strategyThe boxes are in a row from 1 to 100.The persons know EXACTLY in which order they will enter the room and so who will be the next one after them.The first person enters the room by exactly knowing who will be the next. If he got the ring and see his follower name before his name he wears the ring at the LEFT hand and if not he wears the ring at the RIGHT hand and he leaves the room. Without communicating the person can see the ring If the follower saw that the ring is in the left hand, he will repeat the procedure by opening the boxes from 0 while if it was on the right hand he will open the box from 100 to 1. And then switch again and again Go burn to the mountain of fate Sauron !

They can't carry the ring outside....the other followers can't know...weather the person before them found the ring...or not

QuoteOriginally posted by: outrunare they free to open the boxes in any order they want to, or does everyone needs to open them in the exact same order? (you said that the boxes are put in a row)You are on the right track. Yes of course they can open in any order they like. They can even decide on a strategy before hand......All discussions allowed...before whole process starts.

First person 1 enters then person 2....then person.....x...etc...and lastly person 100Boxes are randomly placed....with names 1 to 100 (of course otherwise each one will easily find the ring!)So box 1 can be at 10th position and so on...Hint: Probability associated with permutations cycles

QuoteOriginally posted by: animeshsaxenaThe worst is (1/2)^50.Why that? Do you mean (1/2)^100?In the general case with n people, n boxes, and n/2 peeks per person, one can do slightly better than (1/2)^n:- people with number <= n/2 peek into boxes 1, ..., n/2- people with number > n/2 peek into boxes n/2 + 1, ..., nThis way you get 1 / C(n, n/2). For n = 100 this is around 12.5 times higher than (1/2)^100, but 29% is out of reach. But who said that Sauron is playing fair?

A variant to the problem: what if people are allowed to peek into n-1 boxes? The probability of all people finding their rings can then be made at least ( (n-1)/n) )^n, which converges to 1/e.Again, one can do slightly better by considering permutations. If everybody peeks into all boxes but the one with his own name on it, the probability is the fraction of fixed-point free permutations (derangements), i.e. !n / n!. This expression converges to 1/e as well but stays above ( (n-1)/n) )^n (I guess...). For n = 4 it is 243/768 vs. 288/768.

QuoteOriginally posted by: cm27874A variant to the problem: what if people are allowed to peek into n-1 boxes? The probability of all people finding their rings can then be made at least ( (n-1)/n) )^n, which converges to 1/e.Again, one can do slightly better by considering permutations. If everybody peeks into all boxes but the one with his own name on it, the probability is the fraction of fixed-point free permutations (derangements), i.e. !n / n!. This expression converges to 1/e as well but stays above ( (n-1)/n) )^n (I guess...). For n = 4 it is 243/768 vs. 288/768.I think u got it!Person 1 enters the room...opens first box...finds 4 written on it...so he opens box 4...he finds 10...and he opens 10...it's a permutation cycle.Probability of permutation cycle...is all u need to know...which gives answer > 30%