You and three other people draw cards from a deck and hold them to your foreheads (so that everyone else can see your card, but you can’t). You all guess the suits of your own cards simultaneously. You all win if *at least one* person guesses correctly.
You can all agree on a strategy before drawing cards. What do you do?
(Warning: Spoilers! The post is mostly about finding weirder / more general solutions.)
Plus:
A very incomplete introduction to group theory
Strong opinions about algebraic structures
The worst theorem in math
A stained glass window
I think the linked post manages to avoid mentioning the actually-interesting thing about the problem.
Any given player is guessing their card’s suit with almost no relevant information. (Yes, technically since you’re drawing without replacement seeing a spade is very slight evidence against you having a spade. Ignore that for now, it’s not needed to solve the problem).
This means that any given player is only 1⁄4 likely to get their card’s suit right. Nothing you can do will change that. The goal is not to change that. The goal is to solve the problem in spite of that.
The way to solve the problem, therefore, is not to try to improve any given person’s odds of guessing correctly, but to try to arrange such that the guesses’ correctness is negatively correlated (so when Alice gets it wrong, Bob more often gets it right, and when they both get it wrong, Claire or David will definitely get it right.)
And the more-advanced problem that uses the same concept:
You and three other prisoners have been captured by the Mathematical Problem Prison Warden. As is tradition, he offers you a chance to win your freedom.
All four of you will be placed in a room. Each of you will have a white or black hat on your head (the Warden will flip a coin for each of you independently to determine the color of that prisoner’s hat), and will be able to see everyone’s hat but their own, but will not be allowed to communicate once in the room. You will, however, be able to arrange a strategy in advance.
You must all simultaneously either guess the color of your own hat, or stay silent. If at least one of you guesses correctly and no-one guesses wrongly, you may all go free. But if any of you guess wrongly, or if you all stay silent, the Mathematical Problem Prison Warden will keep you all in prison for the rest of your lives!
What strategy can you and your fellow prisoners follow to get the highest chance of freedom?
What if there are instead 15 of you?
I think you’re right that that’s the interesting part, and I did somehow fail to mention it—except in passing, since it’s the easiest way to prove that every successful strategy has exactly one winning guess.
My solution:
Each person is ignorant between 2 possible states, but each is ignorant between the correct state and a different incorrect state.
We need to partition states so that some (minority) of states are “special” so that if anyone is ignorant as to whether the state is “special” they will guess they are not in the special state, and if they know it isn’t “special” they all stay silent. That way we will lose if the state is special, but will win if the state is not special but someone is ignorant about whether it is special. (What someone does if they know the state is special is not specified, but we’re doomed in this case anyway since others will guess wrong).
Ideally, we need it to be the case in all cases there will be at least one person who is ignorant as to whether the state is special, so that you go free unless the state is special. Then we want to make as there be as few as possible states that are special.
If we imagine the hat arrangements as vertices on a 4-dimensional hypercube, then we want each non-special vertex to be adjacent to at least one (and as few as possible) special vertices. So, the question is, what is the smallest number of special vertices we can use?
So I tried drawing this (with a pair of cubes to represent a hypercube) and it seems you need 4 special vertices (if you only have 3 there are two vertices that are not adjacent to any of them).
Let’s just start with
1) all white hats
being special. Then the other special states can be:
2) prisoner 1 has a white hat and all others have black hats
3) prisoner 2 has a white hat and all others have black hats
4) prisoner 3 and prisoner 4 have white hats and prisoner 1 and prisoner 2 have black hats
All other states are within 1 of at least one of these states, so if everyone follows the strategy, someone will always be ignorant as to whether we are in one of these special states, and we will win if we are not in these 4 states, which is a 75% chance of winning since there are 16 possible states.
Each agrees that if they see two cards of the same suit they will somehow communicate that.
I should’ve specified: no communication allowed between drawing cards and the (simultaneous) guesses.