Just a few really fun puzzles that I’ve come across at one point or another. I really like these ones in particular because they each require some clever thinking to solve effectively.
Puzzle 1: Checkerboard Dominoes
Imagine a checkerboard. It’s easy to see that if you are given 32 1×2 dominoes, you can cover the entire board. However, if I remove two corner pieces as shown, is it possible to cover the remaining board with 31 pieces?
Puzzle 2: Prisoners on Death Row
10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can’t see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone’s head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either “black” or “white”. If what he says matches the color of the hat he’s wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy … this continues until all of the prisoners have been queried.
This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What should they do to save the most lives?
After you have solved the above problem, generalize. There are N prisoners and K different colors of hats.
Puzzle 3: Guess the Number
Two friends are abducted by a gigantic, horned, fire-breathing, man-eating monster named Fred. Now, Fred doesn’t like to eat his victims without giving them a fear fight, so he decides to play a game. In his dungeon he has two rooms, one black and one white. Tomorrow, he will take his stamp maker, and place either a black stamp or a white stamp on each prisoner’s head. The prisoner cannot see the color of the stamp on his own head, but his friend’s. They will be asked to go from their cell into the rooms, one person in each. Now, if either enters the room with the same color as their stamp, they can both go free. But if they both enter the wrong rooms they die. The night before Fred gives them their stamps they are allowed to make a strategy. What strategy should they use to guarantee their life?
And once again, can you generalize to N rooms with N colors?