Hints In A Room

So as a follow-up to my hats in a room puzzle, I'm going to be doing something unusual this time....I'm going to be giving a hint. This puzzle is particularly difficult, and even with this hint it still is quite a trick. Before giving the hint though, lets go through some of the logic that you have probably already gone through.

First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2100). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(100C50) chance of success. This is substantially better than 1/(2100), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.

The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.

I'll finish the entire solution some time later this week.

No comments: