Multiplayer Games

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.

The strategy for the prisoners is to assign numbers \( 1 \), \( 2 \), \( 3 \), \( \dots \), \( 100 \) to themselves.

During the game the prisoner \( i \) makes an assumption that the total sum of all hats is congruent to \( i \) modulo \( 100 \). Under this assumption the prisoner \( i \) will make a guess of his/her hat (he can calculate the total sum of numbers not belonging to him and subtract that number from \( i \)).

Exactly one of the prisoners will make correct guess about total sum and consequently the correct number of his hat.

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.

• (a) Assume that the original position of the switch is off. The prisoners should choose one of them and call him the Boss. The Boss will only flip the switch from on to off, while the others will flip the switch from off to on using the following rule: Each prisoner except for Boss will not touch the switch if it is in the on position or if they flipped the switch already. The Boss will count how many time he flipped the switch and after he has done that 99 times he will announce that the game is over.

• (b) The strategy is modified so that everyone will aim to flip the switch twice instead of once and the Boss will count and end the game after he has flipped the switch 198 times. He can guarantee at that point that everyone has flipped the switch at least once.

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.

The warden can label the bottles using 10 binary digits. That means the first bottle will be labelled as \( \underbrace{0\dots 0}_{9}1 \), the second one is \( \underbrace{0\dots 0}_{8}10 \), etc. the 1000-th bottle is labeled by \( 1111101000 \). After this labeling the warden will make a cocktail for each of his prisoners. Let us label the prisoners by \( 1 \), \( 2 \), \( \dots \), \( 10 \). Then prisoner \( i \) will be served the content of all bottles \( k \) that have the \( i \)-th binary digit equal to \( 1 \).

The next day several prisoners will be drunk - the warden will make a 10-digit binary number whose \( i \)-th digit is \( 1 \) if the prisoner \( i \) is drunk. This \( 10 \)-digit number points to the bottle with wine.

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.

• (a) Let us assign \( 0 \) to red hats and \( 1 \) to green hats. The last person adds up all the numbers modulo 2 and announces the sum (\( 0 \) for red, and \( 1 \) for green). The second to last can determine his/her hat by hearing the total sum and seeing the colors in front. The third to last prisoner can now determine his hat color because he knows the total sum and knows all the colors except his own. This way all the prisoners can be saved.

• (b) The game is the same - now they assign numbers \( 0 \), \( 1 \), and \( 2 \) to the colors and they operate modulo \( 3 \).

• (c) Let us denote by \( (a_1, a_2, \dots ) \) the configurations of hats. Two configurations \( {\bf a} \) and \( {\bf b} \) are said to be in relation \( \sim \) if they differ in a finite number of positions. It is easy to prove that \( \sim \) is an equivalence relation. This equivalence relation partitions the set of all configurations of hats into equivalence classes. The strategy of prisoners consists of choosing a representative from each equivalence class (this is possible according to the axiom of choice).

  Once the game starts each prisoner will be aware of the equivalence class that their configuration is in. The reason is that each prisoner sees all but finitely many hats. Let us denote by \( {\bf t} \) the true configuration of the hats, and by \( \bf{e} \) the representative of the equivalence class of \( \bf{t} \). The last prisoner will count the hats in which \( {\bf t} \) and \( {\bf e} \) differ and announce whether this number is even or odd. The second to last prisoner can determine the color of his hat, and each subsequent prisoner is in the same position as they will have the complete information on colors of the hats of all prisoners except their own.

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.

Players will designate two of them to have special roles: the Boss and the Inspector.

In the beginning of the game each of the players will make a random permutation of the set \( N=\{1,2,\dots, n\} \) and keep that permutation secret from the others. In addition to this, the Boss will create a random permutation of the set \( N^n \).

Then the Boss will repeat the following procedure: For each \( (a_1, \dots, a_n)\in N^n \) he will call the players one by one and he will ask the player \( i \) to pick \( a_i \)-th number from his/her permutation (without telling it to anyone). After each of the players has picked the number, the Inspector will inspect whether the game is over.

A way for inspector to accomplish this task is to choose a random binary sequence \( b \) from the set \( \{0,1\}^n \). Then he arranges all the players in an arbitrary order \( P_1, P_2, \dots, P_{n} \), him being \( P_1 \). The player \( P_1 \) has chosen one number (directed by the Boss), and he will flip the bit corresponding to that number (if the bit were \( 1 \), he will change it to \( 0 \), and vice versa). In such a way player \( P_1 \) has obtained the binary sequence \( b^{\prime} \). Then the player \( P_1 \) will tell the sequence \( b^{\prime} \) to the player \( P_2 \) who will modify the bit corresponding to his chosen number and tell the sequence to \( P_3 \). The players will continue doing this, until all of them have flipped their bits. After that, the player \( P_{n} \) passes the obtained sequence back to the inspector who can easily see whether all the numbers are chosen (they are all chosen if and only if \( P_n \) provided him with the sequence that differs from \( b \) in every coordinate).

Then the Inspector will inform the Boss whether the game is over. If not, the Boss will choose next element from the permutation of \( N^n \) and repeat the same procedure.

Clearly, the game has to finish in finitely many steps.

There is a faster algorithm that accomplishes the assignment of numbers \( \{1 \), \( 2 \), \( \dots \), \( n\} \) to people \( A_1 \), \( \dots \), \( A_n \). Instead of Inspector passing the string of zeroes and ones, the inspector should pass a random string from the set \( \{1,2,\dots, n\}^n \). That means that the string is of length \( n \), and each component is from the set \( \{1,2,\dots, n\} \). The procedure is the same as before, except, when the person \( A_i \) gets a string, he/she modifies it by adding \( 1 \) (modulo \( n \)) to the \( \alpha_i \)-th bit of the string, where \( \alpha_i \) is the number that \( A_i \) has chosen.

This way the Inspector will know exactly which numbers are chosen multiple times and announce that to everyone. Then the inspector can choose the set of numbers that will be assigned to each group of people who chose the same number. Assume that the number \( 1 \) is chosen seven times, and none of the numbers \( \{2,3,4,5,6\} \) is chosen. Then the inspector announces that information, and all those people who picked one should take another random guess of numbers from the set \( \{1,2,3,\dots, 7\} \). The inspector does the same procedure as before, and he/she includes all the people in the procedure. Those who did not pick \( 1 \) should pick the same number as they originally did.

This saves a lot of time. The length of the procedure can be bounded by deterministic bound of order \( n\log n \) by using the Boss in addition to the Inspector in analogous way as described above.