Prisoners and the Glass Signal

Game Theory · Hard · Free problem
A sultan captures 50 wise men and locks them in separate rooms with no way to communicate. Every minute, the sultan calls one prisoner (chosen arbitrarily, with possible repeats) into a room with a single glass on a table. The glass is either upright or upside-down. The called prisoner may flip the glass over, or leave it as is. That is the only action available -- there is no other way to leave messages. The prisoners win their freedom if any one of them declares, "All 50 of us have been called at least once," and the statement is true. If the statement is false, all 50 are executed. Before being separated, the prisoners get one meeting to agree on a strategy. Design a strategy that guarantees the prisoners can eventually make the declaration with certainty. Explain why the strategy is correct and why it terminates.

Open the full interactive solver, hints, and worked solution →