One Hundred Wizards. I first heard this problem from Mira Bernstein.
One hundred wizards are placed in a room. An evil warlock gives them a message. “On the other side of this door is a countably infinite number of boxes, each assigned a natural number. Inside each box is a real number. I am going to send you each into the room one at a time. When you enter, you may open as many boxes as you wish, though you must leave at least one closed. You must then pick up a box which you have not opened, guess what real number is in the box, and then open the box. After you leave, I will reset the room before the next wizard enters, and you will not be allowed to tell any of the wizards anything about your findings in the room. If ninety-nine or more of you correctly identify the number in the box, you will all go free. Otherwise, you will all be killed.” The amount of time that the wizards have to discuss their strategy is an arbitrarily large infinite cardinal number, as is the amount of time that each wizard gets in the room. Can they devise a strategy guaranteeing that they may all go free? If so, what is it? Assume the
axiom of choice.
Click here to see the solution.
Partition the possible sequences of real numbers in the boxes into sets such that two sequences are in the same set if and only if they differ on finitely many entries. Select a representative from each set. When the n-th wizard enters the room, have them sort the boxes into 100 rows, such that the boxes in each row have labels which are increasing and differing buy multiples of 100. Now have the wizard open the boxes in all of the rows except for that containing the label n. Note that for each row of open boxes, there is a representative for the sequence of real numbers it contains. Find the box n whose label is the largest among all boxes whose real numbers differ from their respective representatives. The closed box in the column after that containing B is the one whose containing number we will guess. Have the wizard open every box in the row except for that one. For this row, note that regardless of the value of the closed box, the representative of the sequence found in this row is the same. For our closed box, guess the number found at its position in this representative. A wizard can only guess incorrectly if the last box in their row differs from that row's representative is further to the right as those of all of the other wizards. Such a fate can only befall at most one wizard.
You Light Up for Life, by
Steven J. Miller.