Sharing secret information publicly

[DataGenetics]

(This puzzle originates from the Moscow Math Olympiad)

There are seven cards, numbered sequentially 1-7. The cards are shuffled and dealt (face down) to three people.

Player A receives three cards. Player B receives three cards. Player C receives one card.

Player A looks at his cards and makes a statement that he knows to be true. This statement is heard by all. Then Player B looks at his cards and also makes a statement he knows to be true (also heard by all).

After these two statements have been made, both Player A and Player B know the location of all the cards, but Player C, even though he heard both comments, does not know the location of any of the cards other than his own.

Question: What statements can Player A and B make to accomplish this?

(This does not require any collusion. Player A and Player B have not met beforehand to agree on any secret system).

[Soupspoon]

Instinctive guess:

Spoiler:

...reveal the sum of the cards in one's hands.

A and B (and C, though in that case is unneccessary) know that sum(A1..3)+sum(B1..3)+just(C1) = sum(1...7) and the only unknown after the public 'outing', C1, is calcuable and thus A knows that B's cars are not A's own cards nor the one with C, and B likewise in the opposite direction.

Although there are circumstances where C will also know, from just these facts. Namely if one holder reveals "6" (unique lowest trio) and/or "18" (unique highest) or indeed "7" or "17" or even other numbers where C's card rules out a non-unique answer (e.g. "5+6+9" vs "4+7+9")... So it is possible that an extended version of the puzzle question could have player D (possessing no cards) deriving a full assumption of the locations of all cards, based upon the statement by player C about whether they can answer the question. (Probably would have to be an unqualified affirmative, though.)

[DataGenetics]

You are on the right track, but as you stated, there are some situations, using your strategy, that leaches information to C. You need to come up with a system that does not allow C to learn anything irrespective of what A or B hold.

[Tirear]

You are on the right track, but as you stated, there are some situations, using your strategy, that leaches information to C. You need to come up with a system that does not allow C to learn anything irrespective of what A or B hold.

Spoiler:

Take the sum modulo 7. This ensures that there are multiple hands for each answer, but with three cards you can still figure it out (since C's card has a potential variance of at most 6). For example, suppose A gives 5 as his answer. His hand could be 147, 156, 237, 246, or 345. The card in C's hand will let him rule out two or three of those. Regardless of which card he has, there is no card that would be (or not be, C's card excepted) in all three (or two) possible hands. Hearing B's answer provides C with no new information, as he could figure that out with A's answer plus his card.
I haven't checked all possible sums this way, but expect it should hold up.

Edit: fixed a typo

[MWak]

When you say the "location" of all of the cards do you mean the particular location of each card in each player's hand, or do you just mean which three cards A has, which 3 cards b has, and which card c has regardless of the order in which they hold those cards in their hand. If the order in which the cards are in their respective hands is not required knowledge then I believe I have a simple solution.

[Goahead52]

If you mean that C could not know at least one card hold by A or B then I think that is impossible.
C know for sure the 6 remaining cards once he knows the card he owns.
A and B have to make each one a true statement such as A and B knows what C card have.
Once A and B know what card C have then A and B know what each other have.
How A and B could make statement without revealing at most ONE of their own cards?
If C knows ONE card location then C "wins".

[Cauchy]

The order being required knowledge doesn't make the problem any harder. If you have a solution in which the order is not required, just append the relative values of your three cards in your statement, e.g. "low, high, middle". Anyone who knows your three cards will be able to determine their position, but if I don't know the identity of any of the cards I certainly don't know the identity and position of any of them, and your appended information didn't give me any more information about their identities.

Anyway, Tirear's solution works.

Spoiler:

You can add 1 to each card in the five hands (wrapping 7 around to 1) to get the five hands that sum to a value of 3 greater. Since 7 and 3 are relatively prime, you get all the possible sums this way. (And there should be 7 choose 3 = 35 hands, so we know we've got them all.) So by this inherent symmetry, every possible sum A could say will foil C as long as one of them will. And Tirear already showed that 5 will.

[Goahead52]

Here is the starting statement assuming that A is the first to make a statement :
- A sum his 3 cards and say the sum of my 3 cards is ODD or EVEN
- Hence B by watching his 3 cards could know if the card of C is EVEN or ODD as the sum of the 7 cards is EVEN.
B know for sure if C has (2,4,6) or (1,3,5,7)
As B knows only his 3 cards what should be the statement of B to make A knows the only card of C?

[Sandor]

Spoiler:

Take the sum modulo 7. This ensures that there are multiple hands for each answer, but with three cards you can still figure it out (since C's card has a potential variance of at most 6). For example, suppose A gives 5 as his answer. His hand could be 147, 156, 237, 246, or 345. The card in C's hand will let him rule out two or three of those. Regardless of which card he has, there is no card that would be (or not be, C's card excepted) in all three (or two) possible hands. Hearing B's answer provides C with no new information, as he could figure that out with A's answer plus his card.
I haven't checked all possible sums this way, but expect it should hold up.

Spoiler:

I have checked all possible sums, and it does hold up. For any given card that C holds, there are 6!/3!/3! = 5*4 = 20 different hands that A could hold, and 7 different moduli A could say. The 20 different possibilities are always split 2,3,3,3,3,3,3 with 1 modulus limiting A to 2 possible hands, and the other 6 moduli all limiting A to 3 possible hands.

The cards that C could hold, and the modulus that limits A's hand to 2 possibilities are:
1->3, 2->6, 3->2, 4->5, 5->1, 6->4, 7->0. I'm not sure why that mapping is what it is.

Also, for A and B, just knowing C's card is enough information, and C obviously already knows this. Whatever A says is enough for B to work out C's card, so for any strategy A dreams up, B's reply could just be "C's card is X".

Also^2, there are 7 things A could say, and 7 cards C could hold (which is what B needs to work out based on what A says), so this solution is obviously giving the minimum possible information to C - there can be no better solution, where "better" is defined as telling C less information.

[Tirear]

Spoiler:

Take the sum modulo 7. This ensures that there are multiple hands for each answer, but with three cards you can still figure it out (since C's card has a potential variance of at most 6). For example, suppose A gives 5 as his answer. His hand could be 147, 156, 237, 246, or 345. The card in C's hand will let him rule out two or three of those. Regardless of which card he has, there is no card that would be (or not be, C's card excepted) in all three (or two) possible hands. Hearing B's answer provides C with no new information, as he could figure that out with A's answer plus his card.
I haven't checked all possible sums this way, but expect it should hold up.

Okay, I almost have a proof that this works for all possible deals.

Spoiler:

There are 35 possible hands A could have, and 4 cards remaining that C could have. That gives us 140 distinct deals. From C's perspective, there are 7 cards he could have and 7 answers A could give. This gives us 49 distinct sets of evidence to worry about. C will be able to name the location of a card if all deals that result in a specific set of evidence involve A having that same card. There are three ways we can be sure this doesn't happen:
1. There are no deals that would result in that specific set of evidence. For example, if we weren't taking the modulus of the sum it would be impossible for A to answer "6" and C to have the 1 card at the same time.
2. There are two deals that would result in that specific set of evidence, and they have no cards in common. This happens when A and B give the same answer. C will be able to figure out what the two hands are, but not who has which, so he cannot name the location of a card other than his own.
3. There are at least three deals that would result in that specific set of evidence. Consider two different hands which have two cards in common. They cannot have the same sum because exactly one card is different. One sum cannot be 7 higher because only one card is different and the maximum difference between two cards is six. Therefore they cannot have the same sum modulo 7. Conversely, if two hands down have the same sum modulo 7 then they cannot have two cards in common. With that in mind, consider three different hands which have the same sum modulo 7 and one card in common. Since no two hands can have a second card in common, the remaining cards must be unique. This means that all 7 cards are used in at least one hand. Since C has one card, he will be able to rule out at least one of the hands. Conversely, if there are at least three hands that C cannot rule out after considering the evidence, then they cannot all have a card in common.

I'm pretty sure the modulus ensures that there are no sets of evidence that no deals would fit. Next let's get the two deal cases out of the way. There is one such case for each card C can have, when A and B give the same answer. For even even cards this means that they have the same sum, while for odd cards it means that one sum is 7 greater than the other.
1: 235 467
2: 346 157
3: 126 457
4: 237 156
5: 134 267
6: 137 245
7: 124 356

This leaves 126 deals and 42 sets of evidence. Now if I can prove that it's impossible for four or more deals to fit a single set of evidence, each remaining set will match exactly 3 deals.

FAKEEDIT: While I was typing this someone posted a shorter and complete proof. Well, at least now I know it works.

[Goahead52]

No need to use modulo.
Odd and even sums could solve the problem.
A (or B) when they claim the sum is Even (or Odd) there are 4 possibilities :
If the sum of the 3 cards is even then A (or B) would have :
1. Odd-Odd-Even
2. or Even Even Even

As there are 3 Even numbers (2,4,6) and 4 Odd numbers (1,3,5,7) A and B could not have both EEE and EEE

If the sum of the three cards is odd then A(or B) would have :
3. Odd Odd Odd
4. Odd Even Even

As there are 4 Odd numbers both A and B could not have Odd Odd Odd

We have then :

A claims sum Even : ooe or eee
If A has eee B has Odd sum : ooo
If A has ooe B has either ooe or oee etc....
I let you finish because I`m too sick to continue focusing.

[Tirear]

No need to use modulo.
Odd and even sums could solve the problem.
A (or B) when they claim the sum is Even (or Odd) there are 4 possibilities :
If the sum of the 3 cards is even then A (or B) would have :
1. Odd-Odd-Even
2. or Even Even Even

As there are 3 Even numbers (2,4,6) and 4 Odd numbers (1,3,5,7) A and B could not have both EEE and EEE

If the sum of the three cards is odd then A(or B) would have :
3. Odd Odd Odd
4. Odd Even Even

As there are 4 Odd numbers both A and B could not have Odd Odd Odd

We have then :

A claims sum Even : ooe or eee
If A has eee B has Odd sum : ooo
If A has ooe B has either ooe or oee etc....
I let you finish because I`m too sick to continue focusing.

This doesn't seem to work. Suppose A has 123 and B has 567. Both reveal that their sums are even. Everyone can rule out an eee hand, meaning they must be ooe. A and B can further deduce the values of the odd cards (but C cannot). Unfortunately, there is no way for anyone to figure out which even card any other player has.

[Goahead52]

It does not seem to work because I did not finish my demonstration.
I did not say that once A say sum odd or even what B would say.
I`m still sick but in 2 or 3 days I will post all my demonstration.
Thank you for commenting.

[Goahead52]

While searching on internet I read the solution. I`m not convinced by the solution as the word statement is not clear at all.
In french we say "c`est du n`importe quoi?".
Anyway it happens to me many times the solution is not convincing at all.
And if is a solution then there are many others.
I return to my bed.

[Goahead52]

If this was their solution I really think that is dumb one.
A has 3 cards 1,6,7
He does not know what B has.
He could write down 6 numbers :

1,2,3,5,6,7 by claiming my three cards are among those 6 cards which is true

B has 3 cards : 2,3,5

He will then deduce that C holds the card 4 hence he will claim that C holds 4

A will deduce what B have then.

Why using Fano plane?

Really dumb!!!!

[Cauchy]

The solution that Tirear posted has been proved correct, so you don't have to worry about that. It's quite elegant.

Goahead, your solution can't work. Once A says something, B will never learn any more information, since he already knows the information he's about to say, and that's everything else that gets said. So Tirear's counterexample will foil you no matter what you plan to have B say after A declares an odd or even sum, since B will never be able to distinguish between A having 123 or 134.

Separately, since B needs to know A's cards (and hence C's card) after A's statement, B can name C's card as his statement. This obviously doesn't give C any more information, and it all but explicitly tells A what B's three cards are. So there's no reason that B shouldn't name C's card as his information.

[Goahead52]

I was talking about the solution given on some websites. The solution is using Fano plane.
Just google "russian cards problem". There are many pdf documents about this problem.
The problem has in fact many solutions. In my point of view it is still open for finding the best solution.

[Demki]

If this was their solution I really think that is dumb one.
A has 3 cards 1,6,7
He does not know what B has.
He could write down 6 numbers :

1,2,3,5,6,7 by claiming my three cards are among those 6 cards which is true

B has 3 cards : 2,3,5

He will then deduce that C holds the card 4 hence he will claim that C holds 4

A will deduce what B have then.

Why using Fano plane?

Really dumb!!!!

You could replace the statement "my cards are among 1,2,3,5,6,7" by "I don't have the 4".
If then B has the 4, C immediately knows that, which shows the solution doesn't work

[Goahead52]

If this was their solution I really think that is dumb one.
A has 3 cards 1,6,7
He does not know what B has.
He could write down 6 numbers :

1,2,3,5,6,7 by claiming my three cards are among those 6 cards which is true

B has 3 cards : 2,3,5

He will then deduce that C holds the card 4 hence he will claim that C holds 4

A will deduce what B have then.

Why using Fano plane?

Really dumb!!!!

You could replace the statement "my cards are among 1,2,3,5,6,7" by "I don't have the 4".
If then B has the 4, C immediately knows that, which shows the solution doesn't work

What B has to say or to do to avoid revealing one of his card?

[Goahead52]

Anyway there are soiutions other than the Fano plane (Fano plane was given as solution).
Please google "russian cards pdf" before trying to answer my unfinished solution.

[Goahead52]

Here you can read one the best pdf documents about the russian card problem :

http://cacr.uwaterloo.ca/~dstinson/Wils ... tinson.pdf

[jaap]

If this was their solution I really think that is dumb one.
A has 3 cards 1,6,7
He does not know what B has.
He could write down 6 numbers :

1,2,3,5,6,7 by claiming my three cards are among those 6 cards which is true

B has 3 cards : 2,3,5

He will then deduce that C holds the card 4 hence he will claim that C holds 4

A will deduce what B have then.

Why using Fano plane?

Really dumb!!!!

You could replace the statement "my cards are among 1,2,3,5,6,7" by "I don't have the 4".
If then B has the 4, C immediately knows that, which shows the solution doesn't work

What B has to say or to do to avoid revealing one of his card?

Demski shows that A already reveals too much information in your solution. What he says already allows C to deduce where the 4 is, so it does not matter what B says. What you propose for A to say cannot be part of a valid solution.

[Goahead52]

Here is the solution using Fano plane :

http://www.up.ac.za/media/shared/Legacy ... erman3.pdf

[Goahead52]

If this was their solution I really think that is dumb one.
A has 3 cards 1,6,7
He does not know what B has.
He could write down 6 numbers :

1,2,3,5,6,7 by claiming my three cards are among those 6 cards which is true

B has 3 cards : 2,3,5

He will then deduce that C holds the card 4 hence he will claim that C holds 4

A will deduce what B have then.

Why using Fano plane?

Really dumb!!!!

You could replace the statement "my cards are among 1,2,3,5,6,7" by "I don't have the 4".
If then B has the 4, C immediately knows that, which shows the solution doesn't work

What B has to say or to do to avoid revealing one of his card?

Demski shows that A already reveals too much information in your solution. What he says already allows C to deduce where the 4 is, so it does not matter what B says. What you propose for A to say cannot be part of a valid solution.

I know mister Jaap.
I did it in hurry but my thinking is that no need to use Fano plane. It is not the only solution. This problem could be solved more simply.
Once I found the best and elegant solution I will post it.
I did not exploit my first thought based on odd and even because I was to sick to focus on this problem.

[Cauchy]

Once I found the best and elegant solution I will post it.

Just letting you know, it's already in the thread. Tirear posted most of it, and I put the finishing touches on it.

The Fano plane solution (which you have yet to accurately write down) is pretty, and a natural jump when you're talking about collections of seven discrete things grouped three at a time. It's not as elegant as Tirear's, I'd say. Separately, both of the papers you linked are interested in generalizing the result to larger numbers of cards, so it's possible that a less elegant result than Tirear's is the one that best generalizes.

For those who want to know the Fano plane solution:

Spoiler:

A constructs a Fano plane (a specific arrangement of seven points into a discrete geometry) such that her three cards are one of its lines, and then sends that Fano plane (or says what the seven lines are). C can't figure out A's or B's cards, because upon removing one point, every other point is on exactly two of the remaining four lines (and hence more than 0 and less than 4, so C can't pin any specific card to B (0) or A (4)). B knows that A's line is among the four cards he doesn't have. There will definitely be at least one such line, since A's cards are on a line, and this is the only such line, since to hold two lines there'd need to be 3+3-1=5 points in the set. So B can identify A's cards, and C can't place even a single card. Then, B names C's card, as I described earlier.

[Goahead52]

There is an easy solution :

A will write down 5 cards containing his 3 cards + 2 picked randomly among the remaining 4
B will write down 5 cards containing his 3 cards + 2 chosen depending on his hand and A`s hand
Both A and B will know which card C holds without saying C holds card "x"
C can not know the location of the cards.

I will not put all the possibilities because it is going to take a time.
But the principle of solution is given above.

[Soupspoon]

Both A and B will know which card C holds without saying C holds card "x"

How?
A gave two cards that A does not (yet) have a solid hope of knowing do (or do not) include C's card.

If A gave two cards that C did not, then B possesses these and thus can assume that A's three are the ones not recognised and can reply with his three and (presumably) two of the cards B has worked out A has, to clue A in. But this must be done without saying "I do now know, and know you know", or else C can derive (I think) the one card unmentioned by A that is B's because it is not the one C has, and similarly derive the A card that B never mentioned in return. So for C to remain clueless, there's no additional signalling possible that thus is how it happened.

But if either of the 'not A' cards is the C card then B is given the identities of four 'not B' cards, with no way to differentiate which are A's three and which is C's one. B then can choose his three plus two of the four 'not B' ones, but if B inadvertently picks C's as one of his 'not B' pair, A remains ignorant (and it does not help B). If B does avoid C's, by pure chance, A does know (as B did, above), but needs to clue B in with a further return statement, which (together wirh B's statement) is enough for C to also know, unfortunately...

I've slightly lost track of where we are, but tl;dr;, lists of five (different, but always with the same three of their own) cards keep bouncing back and forward until the person most recently telling of cards works out their partner's, and the partner can work out from the stop that they have information enough even if they didn't previously recognise it. But so will C be able to derive (some, if not all) non-C card positions...

Or do I misunderstand?

[Goahead52]

You are right.
I was totally wrong.
No one to blame other than me.