Solution
The three will discuss their strategy openly, with Eve present. This is important because the order of the statements depends on the deal. And in fact there is a solution requiring only two (not three) statements!
Without even looking at their cards, they have the following conversation.
|
|
|
Alice:
|
I have the perfect strategy. Maybe there are others, but this will work.
Suppose the cards are A1, A2, B1, B2, B3, C1, C2, C3, C4. I choose some card X different from my two and say: "My two cards are among A1, A2, X," where I out these in numerical order. Then the person who has X speaks next.
|
|
|
|
Charlie:
|
I see. If I have X, then I know your cards and so I know everything. I need only make an announcement that will help you and Bob, but not Eve.
Suppose X is C1 (it will be similar for other choices). I'll say the following, putting these three deals in lexicographic order in terms of the card numbers: "The complete deal is one of
A1 A2 // B1 B2 B3 // C1 C2 C3 C4
A1 C1 // B1 C2 C3 // A2 B2 B3 C4
A2 C1 // B2 C2 C4 // A1 B1 B3 C3"
And within each group, the cards will be sorted. The pairwise intersections of the final four have sizes 1, 1, 1; and of the middle three (also the first two), have sizes 1, 1, 1. So Eve will not be able to detect the true family from these three.
To analyze this more carefully, Eve can ask: "Suppose the third of these is the truth, namely,
A2 C1 // B2 C2 C4 // A1 B1 B3 C3
What would Charlie's other two statements be? Following the stated protocol and assuming Alice chose A1 as her extra card, they would be
A2 A1 // B2 B1 B3 // C1 C2 C3 C4 and
A1 C1 // C2 C3 B1 // A2 B2 B3 C4.
This is the SAME list. So the statements would be the same if #3 was the truth, and I cannot distinguish."
So this set of three statements is invariant under the rule. The same invariance holds if the second was the truth. So Eve cannot say which of the three deals I announce is the true one.
(NB: Charlie could just say, "I will add to the true deal a randomly chosen pair of deals from the many possible such pairs that do the job. Then the protocol is nondeterministic and I imagine it would be hard for Eve to learn anything.")
|
|
Bob:
|
And if Alice should choose one of my cards for X, say B1, then I respond with, "The complete deal is one of
A1 A2 // B1 B2 B3 // C1 C2 C3 C4
A1 B1 // A2 C1 C2 // B2 B3 C3 C4
A2 B1 // A1 C3 C4 // B2 B3 C1 C2"
The intersection lengths, from left to right, are 1, 1, 1; 0, 0, 0; and 2, 2, 2. The same invariance property Charlie discussed holds for my choice — so Eve is left in the dark.
|
They then all look at their cards and follow the strategy above. Alice has no B or C, so she knows the true deal. Bob has no C, so he learns the deal if Charlie speaks; while Charlie has no B, so he learns the deal when Bob speaks.
Note that the strategy session might not be necessary.
Suppose when the three get together, they prove that in any successful strategy, it must be Alice who speaks first. But I have no idea whether this is true. There are 1260 possible deals. But given that Alice's list of possible deals must include her two, there are 235 possible deals for her to choose from in her statement. Maybe her assertions can be limited to: "My cards are contained in {A1, A2, X, X, X,...}." In that case, there are only 35 − 2 = 33 possible statements she can make. So maybe there is a way to analyze all possible strategies... and come up with a version of the problem where the strategy session is not necessary.
More details: To be certain this works, let us analyze what Eve learns when she hears Charlie's statements, on the assumption that she knows the exact strategy.
Charlie says this:
A1 A2 // B1 B2 B3 // C1 C2 C3 C4
A1 C1 // B1 C2 C3 // A2 B2 B3 C4
A2 C1 // B2 C2 C4 // A1 B1 B3 C3
Eve can ask: "Suppose the third of these is the truth, namely
A2 C1 // B2 C2 C4 // A1 B1 B3 C3
What would Charlie's other two statements be? Following the stated protocol and assuming Alice chose A1 as her extra card, they would be
A2 A1 // B2 B1 B3 // C1 C2 C3 C4 and
A1 C1 // C2 C3 B1 // A2 B2 B3 C4.
This is the SAME list. So the statements would be the same if #3 was the truth, and I cannot distinguish."
The same holds if the second was the truth. So this set of three statements is invariant under the rule.
And one can easily verify that the same invariance holds if Bob is the second speaker.
[Back to Problem 1227]
© Copyright 2016 Stan Wagon. Reproduced with permission.