Problem of the Week 1226

An Informative Conversation

Three of the seven cards 1, 2, 3, 4, 5, 6, 7, are dealt to Alice and three to Bob, with Eve getting the last card. After examining their cards, Alice makes a public statement, and then Bob does the same.

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

These sorts of problems depend critically on exactly what assumptions are being made. Here we assume that Alice and Bob are strangers (they have had 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. For example, they are at least as smart as you are, and all three know that fact. 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 that Alice should go first.

It can be a little tricky, given a proposed solution, to determine whether or not Eve can learn anything. So I cannot promise to do that for every solution sent to me.

Source: This is known as the Russian Card Problem because of its occurrence in a Russian contest, but it goes back to 1847. I saw it in 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]