Hector's Puzzled

One hundred prisoners are put into 100 completely isolated cells, numbered 1 to 100. Once they are in their cells, they cannot communicate with each other in any way. They are taken by the warden one at a time, but in no particular order, to a special room, Cell 0, in which there are two levers. As the prisoners enter the room, each lever is either up or down, but the levers’ starting positions are unknown. When in the room, a prisoner must flip exactly one of the levers. At any point, any prisoner may declare to the warden that all of the prisoners have been to the room. (The warden will take prisoners to the room indefinitely until someone makes a guess.) If the prisoner is correct, they are all released. If not, they are all executed. Knowing these rules, what strategy can the prisoners devise beforehand that will guarantee their release? How many trips to Cell 0 will it take on average before they are released? [Solution]

Coinball is a contest where two players take turns trying to call a fair coin toss. The game lasts for 100 total tosses, 50 tosses for each player. On each toss, the player calling it announces either “heads” or “tails” and either “rush” or “pass.” If he says “rush,” he gets one point if he calls the toss correctly, and his opponent gets one point if the call is incorrect. Saying “pass” means the toss is worth two points to the caller if he calls the toss correctly and two points to his opponent if he does not. At the end, the player with the most points wins. (The margin of victory is irrelevant; in Coinball, league rankings are based only on wins, with a draw counting as half a win.) If you know your opponent always calls “rush” and you follow the optimal strategy given that knowledge, what are your chances of winning? What if you know your opponent always calls “pass”? If you and your opponent both play optimally, is it better to go first? Or to go second and therefore get the last call? Extra credit: Put your Monte-Carlo simulations away and try to determine the win probabilities to 10 digits of precision. [Solution]

You and three of your friends are on a game show. On stage is a sealed room, and in that room are four sealed, numbered boxes. Each box contains one of your names, and each name is in one box. You and your friends take turns entering the room alone and opening up to two boxes, with the aim of finding the box containing your name. Everyone enters exactly once. Your team can confer on a strategy before stepping on stage, but there is no communication allowed during the show — no player knows the outcome of another player’s trip into the room. Your team wins if it’s ultimately revealed that everyone found the box containing his or her name and loses if any player failed to do so. Obviously, the odds of winning are no better than $50$ percent because any single player has a $50$ percent chance of finding his or her own name. If each person opens two boxes at random, the chance of winning is $(1/2)4=1/16=6.25(1/2)4=1/16=6.25$ percent. Or to put it in technical terms: The chance of winning is not so great. Call this the naive strategy. Your goal: Concoct a strategy that beats the naive strategy — one that gives the team a better chance of winning than $1/16$. Extra credit: Suppose there are $100$ contestants and $100$ boxes. Each player may open $50$ boxes. The chance of winning by using the naive strategy is $1$ in $2^{100}$, or about $1$ in $1.2\times 10^{30}$. How much can you improve the team’s chances? [Solution]

On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin? Extra credit: What if, instead of 60 percent, the doctored coin came up heads some $p$ percent of the time? How does that affect the speed with which you can correctly detect it? [Solution]

You’ll have to click through to see this one . . . [Solution]