Sunday, October 16, 2016

NSA's August 2016 puzzle periodical problem

You can see the statement of an interesting problem I heard recently here.  Basically, it has two parts: a simpler stage, and a more complex setup.

The simpler stage is as follows.  Players A and B both take a card from a standard 52-card French deck and put it face up on their foreheads.  A can only see B's card, and vice versa.  Their task is to guess the color of their own card.  They cannot communicate with each other, and must write down their guesses at the same time.  If at least one of them guesses correctly, they both win.  Is there a strategy that always wins?

The more complex setup has four players, and now they must guess the card's suit.  If at least one of them guesses correctly, they all win.  Is there a strategy that always wins in this case?

SPOILER ALERT

if you want to have at the problem, stop here

So you are still there?  Did you really make an honest attempt at the problem?

.
.
.
.
.
.
.
.
.
.

Ok, so you want to read on.  Fine :).

First, the simpler stage.  Clearly, treating both players as identical doesn't go anywhere.  But if one considers that A's identity is different than B's, one can also assume they behave differently in response to each other's card.  That is, the card they see is a selector for some behavior.  Moreover, both players may have different responses to the same messages.

This looks a lot like ECC with XOR or parity, and RAID disk arrays.  A and B could be stand-ins for error recovery mechanisms that try to reconstruct missing data.  If at least one guesses correctly, together they recover the unknown card.  This metaphor is not precise enough, but it suggests the following strategy.

For example, let's say A guesses A's card is always the same color as B's card (which A can see).  Now if B behaves the same that's not good enough --- so let's have B always guess a color different than that of A's card (which B can see).  Let's say color black is 0, and color red is 1.  Moreover, let CX stand for player X's card color.  With this convention, the approach boils down to:
  • A plays 0 xor CB
  • B plays CA xor 1
A quick check (by hand, the truth table has 4 entries) shows the players always win with this strategy.

If that's what's going on for two colors and two players, what could be a reasonable guess for 4 suits and 4 players?  Well, let the suits be represented by 0, 1, 2 and 3, and further let CX now stand for player X's card suit.  Then,
  • A plays 0 xor CB xor CC xor CD
  • B plays CA xor 1 xor CC xor CD
  • C plays CA xor CB xor 2 xor CD
  • D plays CA xor CB xor CC xor 3
And again, a quick check (with code, the truth table has 256 entries) shows the players always win with this strategy too.

No comments: