up

Wallets and Lockers 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%! I don't know the answer, but various javascript simulations are (way) further down the page. Number of lockers: (must be four) Iterations: Strategy: (0 1 2 3 4 5 6)   strategy 0 is each person looks in two different lockers at random. yields the expected 6.25%. strategy 1 is a basic sliding window approach. - player N looks in lockers N and N+1. yields the expected 8.333%. strategy 2 is everyone looks in the first locker, then looks in the next locker they know no-one else has already looked in. yields about 16% (i don't know the expectation tho) strategy 3 is player N looks first in locker N, then, if they see the wallet of someone who came before them, they look in N-1, otherwise N+1. yields about 20% (i don't know the expectation tho) strategy 4 is weird and best left undescribed as it's really just a botch of strategy 5. yields about 25% (i don't know the expectation tho) strategy 5 is finally cooking with gas ! for those who want to continue figuring it out themselves, i'm not describing it. look at the page source for the function "playerTurnStyle5". yields about 42% (i don't know the expectation tho) strategy 6 is a hamming-function method, which for four people uses the following pattern: 1010 0101 1001 0110 yields the same as the windowing method, about 8.333%. see also this page for a generalization of methods 1 and 5 to N lockers.