Problem of the Week 1227

Another Informative Conversation

Eve will deal two of the nine cards, 1, 2, 3, 4, 5, 6, 7, 8, 9 to Alice, three to Bob, and four to Charlie. Eve then explains the rules and the cardholders can have a public strategy session (that Eve can hear). The rules are that each cardholder can make one public statement, after which the cardholders will know all the card locations, but Eve will not know any card location.

Describe three statements so that they learn each other's cards, but Eve does not learn who has any card.

We assume that Alice, Bob, and Charlie are strangers (no prior communication), and that they make statements that they know to be true (as opposed to statements that might be true by chance). Moreover, they all know that they all know these facts, and they are all smart enough to make any necessary deductions. Also everyone knows (imagine that Eve is the dealer and she states the rules) that this is the protocol to be followed, i.e., the order of the statements. After all, they have had no prior communication, so without this clause, it would not be known who should speak first.

Source: Section 2 of D. Fernandez-Duque and V. Goranko, Secure aggregation of distributed information, 2014; appearing as Puzzle 30 from the new book One Hundred Prisoners and a Light Bulb, by Hans van Ditmarsch and Berteld Kooi, Springer International, 2015, which contains complete discussions of several problems of this type.

[View the solution]