James Tanton has also inspired Simon with his daily puzzles. Below is a set of puzzles all centered around guessing which color your hat is (your life depending on that guess). We spent several hours solving them, and came up with pretty neat life-saving solutions! All these puzzles come from the National Math Festival website, but Simon has rephrased them to suit his style.
— HAT PROBLEMS —
- Warmup: 2 Players
Statement: Albert and Bilbert are playing a game in which either red or black hats will be placed on their heads. Each player will see the color of the other player’s hat, but not their own. At blow of a whistle, each player must guess the color of their own hat. They win if at least one player guessed correctly. What strategy can the players agree upon that will guarantee them a win? - 100 Players and 100 Colors
Statement: The same rules as question 1, except with 100 players and 100 colors! As before, the players will win if at least one guesses correctly. What strategy can the players agree upon that will guarantee them a win? - Waiting it Out
Statement: Albert, Bilbert and Cuthbert, will sit in a circle. Either red or black hats will be placed on their heads. Each player will be asked to raise their hand if they see at least one player with a red hat. Then, only based on the information from the gestures, they will be asked to predict the color of their own hat. They are allowed to keep silent if they aren’t sure. Is there a strategy that the players can agree upon that will guarantee that at least one player will predict correctly? Are there some cases where this is impossible? - How Long to Wait?
Statement: 100 players have either red or black hats. They are told that there’s at least one black hat. They are arranged in such a way that every player can see the color of the others’ hats, but not their own. A clock starts. Every minute, AT MOST ONE player can make a guess as to what color hat they have. If no-one speaks until the 100-minute mark, all players die. If anyone guesses incorrectly, all players also die. What strategy can the players agree upon that will guarantee them survival? - Dark Consequences
Statement: 100 players are arranged in a line. Each player has either a red or a black hat, and they are told that there is at least one black hat somewhere. Because they’re in a line, each player can see the color of the hats of players in front of them, but not behind them. Starting at the back of the line, each player will be asked to either say they have a black hat, or pass. If at least one player says they have a black hat, and they are correct, they all survive! Otherwise, they all die. What strategy can the players agree upon that will guarantee them survival? - Quite Gory
Statement: 10 players are arranged in a line. Each player has either a red or a black hat (there may or may not be a black hat this time). Because they’re in a line, each player can see the color of the hats of players in front of them, but not behind them. Starting at the back of the line, each player will be asked to guess the color of their own hat. If a player guessed right, they’re set free! But if not, they’ll be immediately executed. Players will hear the previous players’ guesses and whether they were right or not. What is the maximum number of players that can be guaranteed to be set free? What strategy can they agree upon that will guarantee that number? - Gory and Confusing
Statement: The same as the previous question, except now there’re 100 possible hat colors instead of 2! - Return to the Option to Pass
Statement: Once again, 10 players are arranged in a line. Each player has either a red or a black hat. This is determined by a coin flip. Because they’re in a line, each player can see the color of the hats of players in front of them, but not behind them. Starting at the back of the line, each player will be asked to either guess the color of their own hat, or pass. Players will hear the previous players’ guesses. If anybody guesses incorrectly, they all die. If they all pass, they all also die. What strategy can the players agree upon that will maximize the chance of survival? - 3 Players, No Information
Statement: 3 players will sit in a circle. A warden will place either a red or a black hat on each of the players. This is determined by a coin flip. Because they’re in a circle, each player can see the color of the hats of the other players, but not their own. At blow of the warden’s whistle, the players will simultaneously guess the color of their own hat or pass. No communication is allowed during the game. If anybody guesses incorrectly, or they all pass, they all die. What strategy can the players agree upon that will ensure a 75% chance of survival? - 2^n – 1 Players, No Information
Statement: 7 players will play the same game as in the previous question, then 15, then 31. Can you devise a general strategy for 2^n – 1 players that will maximize the chance of survival? - 2^n – 1 Players and a Smidgeon of Shared Information
Statement: The same as in questions 9 and 10, except now the players are allowed to guess one at a time. This allows them to hear each other’s guesses before they make their own guess. Does a strategy exist with higher chance of survival now? - Absolutely no Leeway
Statement: 100 players have either red or black hats. This is determined by a coin flip. They are arranged in such a way that every player can see the color of the others’ hats, but not their own. At blow of a whistle, EACH PLAYER must guess the color of their own hat (no passes!) simultaneously. Any player who makes a correct guess survives, any player who doesn’t make a correct guess dies. What is the maximum number of players that can be guaranteed to survive? What strategy can they agree upon that will guarantee that number?
Geeks out of the box 