18
$\begingroup$

Seven cards, numbered $1,2,3,4,5,6,7$, are distributed randomly among three people: Rand gets one of them, Deusovi gets three of them, and Gareth gets three of them. All three know what the seven cards are and how many each person gets, but the only card(s) they can see are their own.

Deusovi and Gareth each post a statement in the Sphinx's Lair. All three people can see the messages, and they know that each speaker knows his statement to be true.

After this, Deusovi and Gareth each know exactly who holds which cards, but Rand still doesn't know the location of any card apart from his own.

No private communication is allowed either before or after the cards are distributed. Deusovi and Gareth can't use the Puzzling mod room or other private rooms to decide a strategy beforehand and encode more information in their messages.

What could the two public statements be?

Of course, the statements can depend on what cards each person holds, but there should be a strategy for what statements to make regardless of the distribution of cards among the three people.

This is based on a puzzle from the Moscow Mathematical Olympiad. It's interesting because there's a nice mathematical answer but also a 'trick' answer whose validity can be debated according to how rigorously the question is phrased. For extra bonus points, find the 'trick' answer - but note that it's NOT , and is still based on pure logic.

Improve this question
$\endgroup$
14
  • $\begingroup$ Deusovi and Gareth - I hope you don't mind me taking your names in vain :-) I just thought it would make the flavour of this puzzle a little fun and interesting. $\endgroup$
    – Rand al'Thor
    Mar 13, 2018 at 0:34
  • 8
    $\begingroup$ I will never forgive you. $\endgroup$
    – Gareth McCaughan ♦
    Mar 13, 2018 at 1:09
  • 2
    $\begingroup$ (Because there's nothing to forgive.) $\endgroup$
    – Gareth McCaughan ♦
    Mar 13, 2018 at 1:09
  • 2
    $\begingroup$ Nothing in this problem statement says that they all know there are seven cards numbered from 1 to 7 and each of them knows the others got the number of cards stated in the statement so they know very little each only what they have. $\endgroup$
    – user2617804
    Mar 14, 2018 at 6:13
  • 1
    $\begingroup$ Something's not clear from the phrasing (“distributed randomly among three people…”): is the question asking for statements that work for any distribution of cards, or something that may happen to work for one particular distribution? And if the former, are you expecting D and G to make the same statement no matter the distribution (which seems too much to ask) or the same kind of statement (whatever that means)? $\endgroup$
    – ShreevatsaR
    Mar 14, 2018 at 8:42

10 Answers 10

Reset to default
14
$\begingroup$

I'm no mathematician, but I think both Deusovi and Gareth can say:

My three numbers sum to N (mod 7)

I'm not sure about making it into a proof, but by the extreme example:

D has 1,2,3: "My numbers sum to 6 (mod 7)"
G & R know his numbers must sum to either 6 or 13
G has 5,6,7: "My numbers sum to 4 (mod 7)"
D & R know his numbers must sum to either 11 or 18
R has 4 but has a pair of possible sums for each of D & G with no further information.
D/G know the other has two possible sums that must be made with the four remaining numbers, which are at most 6 apart limiting which sum is possible.

Basically (maybe/hopefully):

every three numbers will produce two possible sums, but a known set of four numbers can only produce one of them... I think...

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ This is the right answer. Needs a bit more work on the proof though :-) (You can probably make some WLOG assumptions to reduce the number of cases to consider.) $\endgroup$
    – Rand al'Thor
    Mar 13, 2018 at 1:12
  • 5
    $\begingroup$ @Rand - You mathematicians and your need for actual rigorous proofs... when will you learn to just accept "Proof by Alconja Gut" as a valid concept. $\endgroup$
    – Alconja
    Mar 13, 2018 at 1:15
  • $\begingroup$ Right, I've had this sitting in the answer box for a while now, but there's no such thing as an "extreme case". I can't think of a proof that this doesn't leak info. $\endgroup$
    – Deusovi ♦
    Mar 13, 2018 at 1:24
  • 4
    $\begingroup$ If the messages do not need to be posted simultaneously, the second message doesn’t need to be mathematical, it can be just ”rand has a 4”. $\endgroup$
    – Bass
    Mar 13, 2018 at 6:29
  • 1
    $\begingroup$ Any sum-mod-7 has 5 different combinations that can result, and none of these combinations share more than 1 number with each other (since that would mean that the 3rd number would also have to match) This means that number can appear at most 3 times in the combinations. Given a set of 3 random numbers and excluding combinations that contain that number, each eliminate 1 combination for the sum, 1 of them eliminates a second, and the 5th combination contains either 0 or all 3 of the numbers. This lets Deusovi and Garath deduce each other's cards, leaving Rand the remainder $\endgroup$
    – Chronocidal
    Mar 13, 2018 at 17:20
11
$\begingroup$

To complement @Alconja's answer, why they can say:

My three numbers sum to N (mod 7)

For Gareth and Deus to work out each others' hands:

They can work out Rand's card by subtracting the two numbers from 0 mod 7 (since the sum of all the cards is 28, which is 0 mod 7) and finding corresponding card

Why Rand can't work out their hands:

Suppose Rand has the 7 card, otherwise we can add whatever card Rand has mod 7 to all the following possibilities (and 3 times that to the labels).
From above, the other two numbers must be the negative of each other mod 7. So we have 3 cases to consider:
1 and 6: The person who said 1 could have (1,2,5), (1,3,4) or (4,5,6), so Rand can't work out whether anything is or isn't in their hand.
2 and 5: The person who said 2 could have (1,2,6), (1,3,5) or (2,3,4), so similarly Rand can't work out whether anything is or isn't in their hand.
3 and 4: The person who said 3 could have (1,3,6), (1,4,5) or (2,3,5), so once again Rand can't work out whether anything is or isn't in their hand.

This covers all cases, and so we are done.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Was in the process of trying to write up an actual proof, but this is much cleaner that what I had. Nice work. $\endgroup$
    – Alconja
    Mar 13, 2018 at 5:59
  • $\begingroup$ @boboquack , Is mod 7, they only way this can work? Can these 2 both use mod 8 or mod 9 or mod 10 , etc ? Also, what if both choose mods different from each other ? For example, the first guy reports his sum mod 5 and the other guy reports his sum mod 6. Notice that no private conversation is allowed before or after the card distribution so they cannot make a strategy beforehand. $\endgroup$
    – Hemant Agarwal
    Oct 25, 2020 at 11:35
3
$\begingroup$

How about..

Deusovi: The xor of my numbers is [result].
Gareth: The xor of my numbers is [result].

Well my proof hasn't completed yet but..

There is no 3-numbers who has unique xor result.
A small proof: We can always change one bit (in same position) of 2 of the 3 numbers.

EDITED:
It turned out that this solution fails: Rand will know at least one card.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Pardon my ignorance, but how do you define the xor of three numbers? $\endgroup$
    – Rand al'Thor
    Mar 13, 2018 at 1:03
  • 1
    $\begingroup$ @Randal'Thor I believe XOR is associative (aka XOR 2 of them and then XOR the result with the third one) $\endgroup$
    – Quintec
    Mar 13, 2018 at 1:04
  • $\begingroup$ Yes, it's like sum but just replace plus with xor. $\endgroup$
    – athin
    Mar 13, 2018 at 1:06
  • 1
    $\begingroup$ @Randal'Thor Bitwise, I'd assume. $\endgroup$
    – Deusovi ♦
    Mar 13, 2018 at 1:24
  • 2
    $\begingroup$ I think this doesn't work if Rand gets a 7 and one of the announced totals is 1. I don't see a way to get 1 by xoring three numbers from 1 to 6 without using a 6. $\endgroup$
    – D Krueger
    Mar 13, 2018 at 2:31
3
$\begingroup$

Here's an attempt at the 'trick' answer:

Each of them posts "The encryption of the values of my cards Under the public key of [replace with matching name] is [post encrypted value of the cards]"
Deusovi can decrypt Gareth's message and learn his cards and vice versa, but Rand doesn't learn anything thanks to semantic security of the encryption scheme.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nothing so complicated! The 'trick' answer is something that technically works with a slightly less rigorous phrasing of the problem (and was accepted as a solution in the MMO by the examiners who hadn't foreseen it). $\endgroup$
    – Rand al'Thor
    Mar 13, 2018 at 20:45
3
$\begingroup$

For non mathematicians like me, here is a logical answer:

Deusovi says:

"I'm reading a calendar right now but I won't tell you the year nor the month, just that the days of the week corresponding to my numbers are ..." (e.g. Tuesday, Saturday, Sunday). If the three days are all consecutive days, (s)he adds "and (e.g.) Tuesday is an odd (resp. even) number".

This is enough for Gareth to guess Deusovi's numbers. In return, he replies

Then Rand's number is ...

which gives no additional information to Rand but allows Deusovi to deduce Gareth's numbers.

Explanation :

  • The first hint just gives a pattern and for each pattern there are seven possibilities. For example, (Tuesday, Saturday, Sunday) can mean (1, 5, 6) or (2, 6, 7) or (3, 7, 1) or ...
  • From those, Rand can eliminate the possibilities that contain his number but he will always be left with four possibilities and then cannot infer anything
  • On the other hand, in most of the cases, with his three numbers Gareth will be left with only one possibility. The only case when he cannot conclude is if both he and Deusovi have three consecutive numbers (in a circular fashion, with 7 and 1 also being considered consecutive).
  • In such a situation there are two contiguous possibilities which he will disambiguate with the help of the second hint ("Tuesday is odd/even").

    • As for the "trick" answer, my first thought was:

    Deusovi: "all my numbers are odd"
    Gareth: "all my numbers are consecutive"
    Rand is left with two possibilities and therefore can not conclude (not a generic answer though)

    Improve this answer
    $\endgroup$
    2
    $\begingroup$

    I've no proof quite yet, but two statements that seems to work for cases I've tested are

    Deusovi: The sum of my numbers is sum.
    Gareth: The sum of my numbers is sum.

    EDIT: This statement fails for extremes, but I'm leaving it up as I think with a little modification it should work.

    Improve this answer
    $\endgroup$
    3
    • $\begingroup$ You're close, but this won't work if e.g. Gareth's cards are $1,2,3$, because then Rand will know that from Gareth's statement. $\endgroup$
      – Rand al'Thor
      Mar 13, 2018 at 0:43
    • $\begingroup$ @Randal'Thor lol, somehow we sniped each other $\endgroup$
      – Quintec
      Mar 13, 2018 at 0:44
    • 2
      $\begingroup$ @Randal'Thor: I think this highlights a problem with the phrasing of the question. The question asks what could the statements be given certain information, not for a general case that could work no matter how the cards are dealt, just one instance of valid statements. Of course a good answer would be more general but as it stands if they declared their sums to be 12 and 13 then that satisfies all the requirements of the question... $\endgroup$
      – Chris
      Mar 13, 2018 at 12:25
    2
    $\begingroup$

    This is an attempt at the 'trick' answer, assuming that

    the part where "they know that each speaker knows his statement to be true" is actually known by all beforehand, and not deduced by the players from the messages (this is not stated clearly in the question).

    The messages are

    "I don't hold card n" for both of them, where n is the card held by Rand.

    These messages are certainly correct and afterwards, both Deusovi and Gareth know the location of each card, but Rand does not get any additional information.

    Improve this answer
    $\endgroup$
    3
    • 1
      $\begingroup$ You cannot give that message unless you already know Rand's card... Imagine you hold cards 2,3,5 : what would say, exactly ? $\endgroup$
      – Evargalo
      Mar 13, 2018 at 13:03
    • 1
      $\begingroup$ The question does not require Deusovi and Gareth to know the effect of their statement in advance - only that they know it to be truthful. "Oh, I did not get a 4" - "Me neither" are plausible statements that fulfill all requirements (if by chance, 4 is Deusovis card). $\endgroup$
      – Surpriser
      Mar 13, 2018 at 13:46
    • $\begingroup$ This is actually surprisingly close to the intended 'trick' answer, and you get an upvote. But for the correct answer, Deusovi and Gareth's statements are guaranteed to give each other the information they want (the rules-lawyering comes in for the issue of whether or not Rand also learns too much). $\endgroup$
      – Rand al'Thor
      Mar 13, 2018 at 20:48
    2
    $\begingroup$

    Edited to include "trick" solution as given by Rand al'Thor in comments

    I had intended this, but then got confused with what I was writing and ended writing the solution below.

    WLOG Gareth has cards 1, 2 and 3, and Deus 4, 5 and 6. Then they say:

    Gareth: Either I have cards 1, 2 and 3 or you do
    Deus: Either I have cards 4, 5 and 6 or you do

    Then, technically Rand can't work who has which cards, since:

    Gareth could have 4, 5 and 6 and Deus 1, 2 and 3 to logically satisfy the two statements

    But with meta-knowledge, given "everyone knows that Deusovi and Gareth each knows his statement is true" (see comment below), Rand could say:

    Since Gareth didn't know which cards Deus had and they messaged first, if they had cards 4, 5 and 6, they wouldn't know whether Deus had cards 1, 2 and 3 or, say, cards 1, 2 and 7. So Gareth must have cards 1, 2 and 3 and Deus 4, 5 and 6.

    Previous solution

    I don't know whether this is a trick solution, but WLOG Gareth has cards 1, 2 and 3, and then:

    Gareth: I have cards 1, 2 and 3 or cards 4, 5 and 6

    Now, if Deus has cards 4, 5 and 6, they reply:

    Deus: I have cards 1, 2 and 7 or cards 4, 5 and 6

    Otherwise, WLOG Deus has cards 5, 6 and 7, they reply:

    Deus: I have cards 1, 2 and 3 or cards 5, 6 and 7

    Note: in all these answers,

    The order of the two hands and the cards in each hand should be random

    Then Gareth knows what hand Deus has and vice versa because:

    One of the hands in each message will contradict the cards that the other player has

    But Rand doesn't know what card either of them has, because:

    He will have got two messages of the form:
    A: My hand is TUV or WXY
    B: My hand is TUV or XYZ
    so the hands could be A-TUV and B-XYZ or A-WXY and B-TUV.

    This is slightly dodgy/tricky because:

    It relies on asynchronous communication, and Rand finds out one of the hands but doesn't know where it is.

    Improve this answer
    $\endgroup$
    2
    • 1
      $\begingroup$ If Rand has one of the cards either claims he knows everything. Is he holding W or Z in your example? Either way one option is known to be not possible. Only if the first person to speak guesses his partner's hand correctly is there ambiguity. $\endgroup$
      – user19641
      Mar 13, 2018 at 21:53
    • $\begingroup$ This is almost the intended 'trick' solution. This version doesn't have perfect symmetry because Deus might have 5,6,7 after Gareth's statement; the exact statements I was thinking of were (WLOG Gareth has 1,2,3 and Deus has 4,5,6) Gareth: "Either I have 1,2,3 or you do." Deus: "Either I have 4,5,6 or you do." This doesn't work as a solution only given the restriction that everyone knows that Deusovi and Gareth each knows his statement is true. With that restriction (not stated in the original MMO puzzle), Rand can use meta-knowledge to deduce the others' cards. $\endgroup$
      – Rand al'Thor
      Mar 14, 2018 at 0:41
    0
    $\begingroup$

    Working off of Alconja's answer,

    They both announce their sum in mod 7. It is clear that the sum of all the numbers from 1 to 7 is 0 mod 7. Suppose that Desouvi and Gareth say their sums in mod 7, called d and g respectively. Then, since the sum of all the numbers is 0 mod 7, d+g+r=0 mod 7 so r=-d-g mod 7. This means that they will all know the card that Rand has. Then, in Desouvi and Gareths perspective, they know their own cards and they know Rand's card, so they will know the other persons cards as well. However, In rand's perspective, he only know what the sums of the numbers mod 7 of the other two players are. He will not be able to deduce the numbers on the other peoples cards because of the sheer amount of possiblities that they can have.

    Improve this answer
    $\endgroup$
    2
    • $\begingroup$ :o Why the -1?? $\endgroup$
      – Praneetmek
      Mar 13, 2018 at 21:00
    • $\begingroup$ I didn't downvote, but "sheer amount of possiblities" isn't very rigorous. $\endgroup$
      – boboquack
      Mar 13, 2018 at 21:07
    -1
    $\begingroup$

    Just the proof for Alconja’s Answer
    Ex. 1

    D has 1, 2, 3: My numbers sum to 6 (mod 7)
    G & R know that they either sum to 6 or 13
    G has 5, 6, 7: My numbers sum to 4 (mod 7)
    D & R know that they either sum to 11 or 18.
    D can then subtract his sum (6) from the total (28) to get 22
    D then checks and sees that because $22-11=11$, and there is no 11 card, G’s numbers must sum to 18. $22-18=4$, so R has the 4 card.
    G then does the same. $28-18=10$, there’s no -3 card so D can’t sum to 13, must sum to 6. $10-6=4$, R has the 4 card.
    G & D now both know their own cards and R’s card, and by elimination know each other’s

    Ex. 2

    D has 3, 4, 7: My numbers sum to 0 (mod 7)
    G & R know that they either sum to 7 or 14
    G has 1, 5, 6: My numbers sum to 5 (mod 7)
    D & R know that they sum to 12 (can't sum to 5 because the lowest #'s are $1+2+3$, which equals $6$
    D does quick math, $14+12=26$, $28-26=2$, R has 2. D now knows all cards.
    G does math, $12+7=19$, $28-19=9$, can't be right. $12+14=26$, $28-26=2$, R has 2. G now knows all cards.

    R remains clueless throughout both examples

    Improve this answer
    $\endgroup$
    6
    • $\begingroup$ This isn't a proof, just a demonstration. It's pretty clear that it gives me and Gareth each others' cards: what we don't know is whether it leaks info. $\endgroup$
      – Deusovi ♦
      Mar 13, 2018 at 4:40
    • $\begingroup$ @Deusovi updated with another example, this time with a mod that only has one possible sum. It still leaks no info, as there are more than one ways to make a number $\endgroup$
      – TrojanByAccident
      Mar 13, 2018 at 4:50
    • 4
      $\begingroup$ This doesn't constitute a proof though. These are just examples. The entire point is that we're trying to prove that it never leaks information. $\endgroup$
      – Deusovi ♦
      Mar 13, 2018 at 4:53
    • $\begingroup$ @Deusovi is that even possible without brute-forcing all possibilities? $\endgroup$
      – TrojanByAccident
      Mar 13, 2018 at 4:54
    • 1
      $\begingroup$ If it's from a math olympiad, it should be! The only question is how. $\endgroup$
      – Deusovi ♦
      Mar 13, 2018 at 4:55

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

    Not the answer you're looking for? Browse other questions tagged or ask your own question.