NSA’s 2016 Puzzle Periodical - August Solution (Part 1)

This month’s NSA Puzzle periodical can be found here. It’s a 2 part puzzle, and I’ve only solved the first one so far, so this will be a 2 part post.

The copyright status of the actual puzzle text is unclear, so this is a paraphrase.

Ava and Bruce are playing a game. They each take a random card from a standard deck of cards, put their card on their forehead (so the other person can see it), and then write down a guess for which colour their own card is. If one of them guesses correctly, they win the game. Otherwise, they lose. They can’t communicate after having taken a card, but they’re allowed to form a strategy ahead of time which will guarantee that they win. What’s the best strategy?

The solution is fairly straightforward: Bruce will write down the guess for his card to be the opposite of Ava’s card (e.g. if she has red, Bruce will guess black). Ava will guess her colour to be the same as Bruce’s card (e.g. if Bruce has a black card, Ava will guess black).

The following is a table of possible cards and guesses, and their success using this strategy. Guesses with an asterisk are the ones which were correct.

Bruce’s Card Ava’s Card Bruce’s Guess Ava’s Guess Win
Black Black Red Black* Y
Red Black Red* Red Y
Black Red Black* Black Y
Red Red Black Red* Y

Thought process

This section contains everything I thought and tried, so it’s not organized in any particular way. I expect my thoughts aren’t 100% correct and there’s probably another solution I missed, but this is how I arrived at the solution above.

If both Ava and Bruce choose one colour by default (e.g. red), and only one can switch, then if Bruce sees that Ava has a black card, he knows she’ll make an incorrect guess, and if she has a red card, he knows they’ll win regardless of his guess. In the first case, however, there’s nothing he can do since he still has no idea what colour card he has.

Since having one person with a fixed guess leaves the other person helpless knowing the first person will get it wrong, we need to either give both players the ability to change their guesses, or give one of the players a specific way of changing their guess which depends on their own initial guess.

My first attempt along this path is this: Bruce will choose black, Ava will choose red. If either sees the other will be wrong, they’ll switch their colour. This strategy leads to the following table.

Bruce’s Card Ava’s Card Bruce’s Guess Ava’s Guess Win
Black Black Red Red N
Red Black Black Black* Y
Black Red Black* Red* Y
Red Red Black Black N

As we can see from the above table, the incorrect solutions were caused when both players had the same colors. In those cases the person who had the correct guess ended up switching to the wrong color.

If we look at the table of the last attempt we can notice that if we have Ava always pick red, we’re guaranteed to have 2 wins, and we can get a third if we have Bruce switch his guess if Ava will guess wrong (i.e. when Ava has black). This gets us a bit closer to a full solution, as the following table shows us.

Bruce’s Card Ava’s Card Bruce’s Guess Ava’s Guess Win
Black Black Red Red N
Red Black Red* Red Y
Black Red Black* Red* Y
Red Red Black Red* Y

Now given the above table, it is clear that they could’ve won the first instance is if Ava switched her guess to black. However, all she knows that would allow her to make that decision is the fact that Bruce has a black card; she doesn’t know what her card is so she can’t know what Bruce will guess. We note, however, that the only other instance when Bruce has a black card is the third line, where Bruce will guess correctly. So if Ava switches to black in that case, they still win.

So our final solution is the same as the last one, except that Ava will switch her guess to black if Bruce has a black card. This gets us the following table full of wins!

Bruce’s Card Ava’s Card Bruce’s Guess Ava’s Guess Win
Black Black Red Black* Y
Red Black Red* Red Y
Black Red Black* Black Y
Red Red Black Red* Y

To come up with a simple way of writing up the solution, we’ll note that Bruce is effectively guessing his card to be the opposite of Ava’s, and Ava is guessing that her card’s the same as Bruce’s.

The next part

The next part of this puzzle involves 4 people guessing the suits of their own cards (which means 4 choices). I expect the idea is to adapt the strategy in the first part to 4 people, but I don’t see how right now. I’ll have to think about it some more and maybe post the second part tomorrow!