I collect riddles like these! Here are a few of them.
Numbered Hats
A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success?
Colored Hats
A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?
Coins on a Chessboard
A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?
Ah, the Colored Hats is awsome (Haven't tried the other ones, thanks for those)!
It gets even more interesting by using three colors instead of two. The solution stays the same in principle, but [guvaxvat zbqhyb guerr vf n ybg yrff boivbhf guna jbexvat jvgu rira naq bqq.] (ROT13)
When the prisoners are together, they assign each person a unique ID from 1 to 100.
Once the round starts, each looks around and adds up the total on everybody else's hat, mod 100. Suppose you see a total of h (mod 100). Then you should make a guess g = h - your ID (mod 100).
With 1000 repeated experiments of 1000 trials each, this saved the prisoners ~ 630±17 ~= 63±2 percent of the time.
If each person just guesses a random number you succeed the same amount of the time. You have a 99% chance of guessing wrong. The chance of 100 people guessing wrong is 0.99 ^ 100. So the chance of at least 1 person guessing right is 1 - 0.99 ^ 100, which is 63.4%.
There's a strategy that guarantees success. And you're so very close to it. So close, in fact, that I'm going to guess you've heard this before and just don't fully remember the solution.
The first one makes a sacrifice and says the color of the next hat. He has a 0.5 chance. The next person thus has a chance of 1. The third has to make a sacrifice again. Naively that is an average 0.75 chance over all. An exact calculation is too complicated for my taste.
Call the sum of all assigned numbers N. No prisoner knows N, but they do know that there are exactly 100 possible last two digits of N, from "00" up to "99". Beforehand, assign a different last digit pair to each prisoner. When the prisoner guesses, he sums everybody else's number, then guesses the number between 1 and 100 that, when added to his partial sum, results in his assigned last two digits.
That's much cleaner than I thought it would be. I was convinced that there was a solution that guaranteed success, since each arrangement of numbers could get mapped to a unique guessing strategy, so if you could make it so that exactly one correct guess per arrangement you're golden. I tried working with a N-wide N-dimensional cube, got it working for N=2, and failed at N=3.
This makes sense, though twhb didn't mention any restriction on the numbers you might guess. Thus the first prisoner could just guess on the entire sum they saw, and only two guesses would be needed.
Numbered Hats
A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success?
Colored Hats
A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?
Coins on a Chessboard
A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?