Sharing secret information publicly
Moderators: jestingrabbit, Moderators General, Prelates
- DataGenetics
- Posts: 24
- Joined: Sat Jan 01, 2011 1:12 am UTC
- Location: Seattle
Sharing secret information publicly
(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).
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
- You have done something you shouldn't. Or are about to.
- Posts: 3877
- Joined: Thu Jan 28, 2016 7:00 pm UTC
- Location: 53-1
Re: Sharing secret information publicly
Instinctive guess:
Spoiler:
- DataGenetics
- Posts: 24
- Joined: Sat Jan 01, 2011 1:12 am UTC
- Location: Seattle
Re: Sharing secret information publicly
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.
Re: Sharing secret information publicly
DataGenetics wrote: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:
Edit: fixed a typo
Re: Sharing secret information publicly
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.
My IG: Standup Comedy, Vinyl, Beards, Philosophy
GoatVsFish IG: In the beginning, there was GoatVsFish
The Joy of Drinking: Drunk painting with Bob Ross
GoatVsFish IG: In the beginning, there was GoatVsFish
The Joy of Drinking: Drunk painting with Bob Ross
Re: Sharing secret information publicly
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".
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".
Re: Sharing secret information publicly
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.
Anyway, Tirear's solution works.
Spoiler:
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Sharing secret information publicly
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?
- 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?
Last edited by Goahead52 on Tue Aug 09, 2016 4:46 pm UTC, edited 1 time in total.
Re: Sharing secret information publicly
Tirear wrote:Spoiler:
Spoiler:
Re: Sharing secret information publicly
Tirear wrote:Spoiler:
Okay, I almost have a proof that this works for all possible deals.
Spoiler:
FAKEEDIT: While I was typing this someone posted a shorter and complete proof. Well, at least now I know it works.
Re: Sharing secret information publicly
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.
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.
Re: Sharing secret information publicly
Goahead52 wrote: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.
Re: Sharing secret information publicly
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.
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.
Re: Sharing secret information publicly
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.
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.
Re: Sharing secret information publicly
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!!!!
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!!!!
Re: Sharing secret information publicly
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.
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.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Sharing secret information publicly
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.
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.
Re: Sharing secret information publicly
Goahead52 wrote: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
Re: Sharing secret information publicly
Demki wrote:Goahead52 wrote: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?
Re: Sharing secret information publicly
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.
Please google "russian cards pdf" before trying to answer my unfinished solution.
Re: Sharing secret information publicly
Here you can read one the best pdf documents about the russian card problem :
http://cacr.uwaterloo.ca/~dstinson/Wils ... tinson.pdf
http://cacr.uwaterloo.ca/~dstinson/Wils ... tinson.pdf
Re: Sharing secret information publicly
Goahead52 wrote:Demki wrote:Goahead52 wrote: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.
Re: Sharing secret information publicly
jaap wrote:Goahead52 wrote:Demki wrote:Goahead52 wrote: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.
Re: Sharing secret information publicly
Goahead52 wrote: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:
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Sharing secret information publicly
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.
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
- You have done something you shouldn't. Or are about to.
- Posts: 3877
- Joined: Thu Jan 28, 2016 7:00 pm UTC
- Location: 53-1
Re: Sharing secret information publicly
How?Goahead52 wrote:Both A and B will know which card C holds without saying C holds card "x"
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?
Re: Sharing secret information publicly
You are right.
I was totally wrong.
No one to blame other than me.
I was totally wrong.
No one to blame other than me.
Who is online
Users browsing this forum: No registered users and 9 guests