up

Wallets and Lockers - take two This comes from Michael Plotz, who i believe got it from his cousin, Peter Winkler. Rules There's a building with a room with four lockers in it. There's another room in the building with a team of four people in it. Each locker contains exactly one wallet which belongs to exactly one of the four people. Now, one at a time, each person on the team gets to go into the locker-room alone, and look in at most two of the lockers. Then, after only looking, they close the lockers and leave the whole building. They're not allowed to move wallets, leave notes, or in any way communicate with their teammates once they've entered the locker-room. The team wins if and only if every person on the team sees their wallet. It's impossible to come up with a strategy which guarantees each person will see their wallet, but some strategies have a higher probability of winning than others. (for example, if everybody looks in the same two lockers, the probability of everyone seeing their wallet is zero.) According to Michael, there's a strategy which gives the team about a 41% chance of winning! (the naivest approach yields, i think, about 12.5%) How about 100 lockers, people, and wallets, and each person gets to open 50 lockers ? Again according to Michael, the same method yields about 30%! Number of lockers: (must be even) Iterations: Strategy: (1 5)   note that with high N and Iters, simulation can take a while and you'll probably get a pop-up from your browser telling you that a script is hogging your machine. Let the script run. strategy 1 is a basic sliding window approach. - player P looks in lockers P thru P+(N/2). yields about 8% for N = 4, 0.2% for N = 10, and 0% for N = 100. strategy 5 is finally cooking with gas ! yields about 42% for N = 4, 30% for N = 100, and 29% for N = 1000! see also this page for strategies 0, 2, 3, and 4, but only with four lockers.