A puzzle by Ben H., a systems engineer at the National Security Agency, from the agency’s August 2016 Puzzle Periodical:
At a work picnic, Todd announces a challenge to his coworkers. Bruce and Ava are selected to play first. Todd places $100 on a table and explains the game. Bruce and Ava will each draw a random card from a standard 52-card deck. Each will hold that card to his/her forehead for the other person to see, but neither can see his/her own card. The players may not communicate in any way. Bruce and Ava will each write down a guess for the color of his/her own card, i.e. red or black. If either one of them guesses correctly, they both win $50. If they are both incorrect, they lose. He gives Bruce and Ava five minutes to devise a strategy beforehand by which they can guarantee that they each walk away with the $50.
Bruce and Ava complete their game and Todd announces the second level of the game. He places $200 on the table. He tells four of his coworkers — Emily, Charles, Doug and Fran — that they will play the same game, except this time guessing the suit of their own card, i.e. clubs, hearts, diamonds or spades. Again, Todd has the four players draw cards and place them on their foreheads so that each player can see the other three players’ cards, but not his/her own. Each player writes down a guess for the suit of his/her own card. If at least one of them guesses correctly, they each win $50. There is no communication while the game is in progress, but they have five minutes to devise a strategy beforehand by which they can be guaranteed to walk away with $50 each.
For each level of play — 2 players or 4 players — how can the players ensure that someone in the group always guesses correctly?
|
SelectClick for Answer |
The 2-person case is simpler. Let r denote a red card and b denote a black card. Let’s list Bruce’s card’s color first. Then the 4 distinct possibilities are rr, bb, rb, and br. The following strategy is foolproof. Bruce guesses that his card is the same color as Ava’s (covering the cases rr and bb). Ava takes the opposite approach and assumes that her card’s color is different from Bruce’s (covering the cases rb and br). One of them will necessarily be correct. If Bruce and Ava properly employ these strategies, they cannot lose the game.
Before diving into the 4-person case, let’s reexamine the 2-person case. We could interpret a red card as a 0 and a black card as a 1. Then Bruce’s strategy, as described above, handles the cases 00 and 11. His strategy could be interpreted as “the sum of our cards is even.” (0+0=0, 1+1=2) In this language, Ava’s strategy would be “the sum of our cards is odd.” Again, one of them must be right, no matter the cards. Note that Bruce and Ava have divided the sample space of all possible outcomes into 2 cases, based on the sum of the cards.
The 4-person case is more general and depends upon the notion of modular arithmetic, and in particular remainders when dividing by 4. Rather than purely guessing “the suits are the same,” or “the suits are different,” the players must be more clever. Let’s map each suit to a number. Clubs are 0, diamonds are 1, hearts are 2, and spades are 3. So, if Emily looks out and sees hearts (Charles), hearts (Doug), and spades (Fran), she interprets this as 2+2+3=7. Suppose that Emily’s card’s suit is clubs, which she obviously doesn’t know. Consider the following strategies:
- Emily guesses her suit so that the total sum is a multiple of 4. She sees hearts, hearts, spades and guesses diamonds (2+2+3+1=8).
- Charles guesses his suit so that the total sum is 1 more than a multiple of 4. He sees clubs, hearts, spades and guesses clubs (0+2+3+0=5).
- Doug guesses his suit so that the total sum is 2 more than a multiple of 4. He sees clubs, hearts, spades and guesses diamonds (0+2+3+1=6).
- Fran guesses her suit so that the total sum is 3 more than a multiple of 4. She sees clubs, hearts, hearts and guesses spades (0+2+2+3=7).
In this example, Fran guesses correctly because the total sum is 7, which is 3 more than a multiple of 4. For any combination of suits, one of them must be right. After all, the total sum must be a whole number. And all whole numbers have remainder 0, 1, 2, or 3 when divided by 4. As long as each of them sticks to his/her strategy, the group can ensure they won’t lose the game. Interestingly, it doesn’t matter which numbers they choose to use, as long as they all have different remainders when divided by 4. So, choosing any four consecutive whole numbers is a sufficient mapping.
|
