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. 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. 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
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:
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. 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.
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:
Players are only conducting conversations involving two people. Others cant 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.)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. |
2005-2018 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |