Multiplayer Games

Problem 1

There are 100 prisoners in a prison. A warden has decided to play the following game. He puts a hat on the head of each of the prisoners, and each hat contains a number from the set \(\{1,2,\dots, 100\}\). Different prisoners may or may not have the same numbers on their heads. Each prisoner can see all of the hats except for his/her own. Then prisoners are asked to write down the number on their hats. If at least one of them guesses the number correctly then they are all free. If all of them are incorrect then they are considered losers and politely asked to feel bad about that.

Before the game started the prisoners had a chance to talk and develop a strategy. The warden listens for the strategy and will take advantage of any flaw in it to make the prisoners lose.

Prove that there is a strategy for prisoners that guarantees their victory.

Problem 2

There are 100 prisoners in a prison. A warden is taking prisoners one by one to a room with a single switch in it. The switch has two positions (on and off). While in the room, each prisoner is allowed to change the position of the switch or to say ``Everybody was in the room already.’’ Once that sentence is said the game ends. If the sentence is true, all prisoners are set free; however if it is false, all of them are punished.

The warden has an ordered list in which the prisoners are taken to the room, and each prisoner appears infinitely many times in that list. However, it is up to a warden to arrange the prisoners in the list. For example, he can schedule to take Al Capone million times, and schedule others only afterwards, so Al Capone would make a mistake by prematurely saying the above proposition.

Before the game starts the prisoners had right to decide on strategy, but the warden is listening to the strategy and if there are any flaws in it, he will use them to his advantage. Prove that there is a strategy that can guarantee that the prisoners can be saved, if

  • (a) The initial position of the switch is known to the prisoners.

  • (b) If the initial position of the switch is unknown to the prisoners.

Problem 3

There are 10 prisoners in a prison. A warden has 1000 bottles of grape juice: 999 of them are real, honest grape juice, but one of is fake and contains wine instead. Let’s assume for the purposes of this problem that the following two conditions are true:

  • (i) Noone is able to recognize wine by taste, color, or weight;

  • (ii) Whoever drinks even a drop of wine in the evening will end up being seriously drunk the next morning.

Prove that using these 10 prisoners the warden can find out which bottle contains wine after only one night.

Problem 4

There are 100 prisoners in a prison. A warden has decided to play the following game: He will arrange all prisoners in a row, all of them facing the same direction. Then he puts hats on heads of the prisoners. Each hat can be red or green. No prisoner can see his/her own hat nor any of the hats of people behind. Thus, the first prisoner in the row doesn’t see any hats, the second one can see the hat of the first, and so on. The last prisoner can all hats except his (or hers).

After this initial setup is completed, each prisoner has right to say one word: red or green. If that is the color of his hat, the prisoner is free - otherwise the prisoner will face a cruelty of some sort.

The night before the game the prisoners have a chance to talk and design the strategy to save as many of them as possible.

  • (a) Prove that there is a strategy that can guarantee that 99 of the prisoners can be saved.

  • (b) Solve the analogous problem in which the hats can be red, green, or blue.

  • (c) Solve the analogous problem in which the hats can be red or green, but the number of prisoners is infinite. In this one, you need to prove that there is a strategy that can guarantee that everyone except the last one in the row is saved.

Some frequently asked questions. The warden is present at the party in which the prisoners are designing the strategy. If the strategy has any inefficiencies the warden will choose such an arrangements of hats so as to maximize the number of unsuccessful prisoners.

Prisoners have excellent eyesight and excellent hearing. They can see and hear to infinite distances. However, they are not allowed to cough, throw eggs at each other, or use any verbal or non-verbal signs. They are only allowed to say the color of their hat.

Problem 5

Let \(n > 3\) be an integer. There are \(n\) players who are only allowed to conduct conversations each involving exactly two persons. The goal of the game is for each player to choose one number from the set \(\{1,2,\dots, n\}\) so that:

  • (i) Each of the numbers \(1,2,\dots, n\) is chosen by exactly one player.

  • (ii) For any two different players \(A\) and \(B\), \(A\) knows only his own number, and knowing that number, \(A\) can’t guess what was chosen by \(B\) with a probability greater than \(\frac1{n-1}\).

Players are only conducting conversations involving two people. Others can’t hear the content of a conversation, but everyone is aware of every conversation that is taking place.

Prove that there is a positive integer \(D\) (depending only on \(n\)) such that the players can finish the game in less than \(D\) conversations.

You are allowed to assume that each player has perfect memory, and that each player has a perfect random number generator.

(problem made by Andrew Critch et al.)