Is it possible to win this game?

s it possible to win this game?

---

The game

---

You have two players, a Guesser and a Tester. The Tester draws two random cards in a deck of standard playing cards (not including jokers) and looks at the cards without showing the Guesser. In order for the Guesser to win the game the Guesser must deduce with 100% certainty the suit of any one of the Testers cards. The Guesser can ask any yes or no question they like and the Tester answers each question the following way:

1. Look at the first card, ignoring the second card, and ask the question with just the first card in mind. 
2. Now look at the second card, ignoring the first card, and again ask the question but this time only keeping the second card in mind.
3. Decide which answer (1 or 2) you wish to say to the Guesser such that the Guesser gets as little information as possible.

An example, suppose the Tester picked up a hearts and a clubs, if the Guesser asks "Do you have a hearts card?" The guesser would do the following:

1. Look at just the hearts card and ask "Do I have a hearts card?". Answer is yes.
2. Look at just the clubs card and ask "Do I have a hearts card?". Answer is no.
3. Decide to say No (2) to give the Guesser as little information as possible.

The question is can the Guesser always win no matter what the Tester answers?

---

Answer

---

Let's find out. For the proof we'll call the suits of the cards H (hearts), C (clubs), S (spades) and D (diamonds).

Getting rid of the trivial case

First thing we notice immediately is that if the Tester picks up two cards of the same suit then the question is trivially resolved because the Guesser will be forced to answer "Yes" if the Guesser asks if they have a card of that suit. For example if the Tester picked up two hearts and the Guesser asked "Do you have two Hearts?" the Tester looks at both cards individually and both times he is forced to say yes. So for the remainder of this proof we're going to assume the Tester picks up two cards of different suit.

What questions should we be asking

The second part of this is to ask ourselves what questions we should really be asking and what questions the Tester can take advantage of. The first thing we get from the example is that asking for any one particular suit will give no information because the Tester will always be able to say no. One might be tempted to ask a question like "Do you have a hearts AND a spades?" but this question is does not make sense to the Tester and he'll always have to say no. He might look at his Hearts card and ask "Is this both a hearts and a spades?" and the answer is clearly no, it is just a hearts card, so asking whether the tester has both a hearts and a spades card will yield no results. The answer that gives information is not to ask whether the Tester has a hearts and a spades but to ask whether the Tester has a hearts OR a spades, if he has both he'll be forced to answer yes to this question. It only works with two suits though because if you asked whether he had one of three suits (Hearts, clubs and diamonds) he will always have one card in the list and so will always be able to say yes, giving no information.

So now we have some questions to answer, we can go through all six possible combinations of two suits and ask whether the Tester has one OR the other. The Tester will be forced to say Yes to the question that contains both his suits and No to the question that contains neither of his suits, but what about all the other 4 questions? For those 4 he can say whatever he wants. Lets draw up a truth table to describe the possible answers a Tester can give, in this case we will assume the Tester has a H (hearts) and a S (spades)

The truth table is really large because there's 24 different options the Tester can choose from so to narrow it down we'll cut out three obvious cases. The first two cases are obvious.

The Tester says No to every combination except the one he's forced to say Yes to:

In this case it's trivial, we simply pick any one of the two suits for the question he said yes to, he's given away the answer!

The Tester says Yes to every combination except the one he's forced to say No to:

It's simply the negation of our first example, pick any suit outside of the two suits in the combination he said no to. He's given away the answer but in a more roundabout way.

The Tester has said Yes to two combinations but has said No to every other combination:

This one may seem more difficult but it's also trivially solvable. The two combinations that he said Yes to will have to have a common suit and so whatever that common suit is, is the suit that they have. So for example if they said yes to H / C and H / S then it's clear that H is a suit that they have!

Ok so now that we've gotten the easy scenarios out of the way lets talk about the harder scenarios

The Tester has said No to two combinations but has said Yes to every other combination:

This time we can safely determine a suit that the Tester definitely does not have but we can't determine which of the three remaining suits the Tester does have. Let's draw a truth table of possible outcomes to illustrate this point:

Iteration	H / S	H / C	H / D	S / C	S / D	C / D
1	Yes	Yes	Yes	Yes	No	No
2	Yes	Yes	Yes	No	Yes	No
3	Yes	Yes	No	Yes	Yes	No
4	Yes	No	Yes	Yes	Yes	No

In iteration 1 and 3 we can see that Diamonds is the shared suit in the No's so we can definitely say they don't have a diamonds. In iteration 2 and 4 we can see that clubs is the shared suit so we know they definitely don't have a clubs. What we can now is fairly easy, look for a suit combination that is a Yes but contains our excluded suit. For example in iteration 1 we've discarded Diamonds, which means that when he said Yes to the Hearts or Diamonds question, we know that he MUST have a hearts because he CAN'T have a diamonds. For iteration 2 we see he doesn't have a clubs but we also see he said yes to whether he had a clubs OR a hearts so again, we know he has a hearts! It requires a little bit more work but it's fairly obvious when we think about it. Finally we have our final possibility.

The Tester says Yes to half the combinations and No to the other half

This is when the Guesser runs into problems

Iteration	H / S	H / C	H / D	S / C	S / D	C / D
1	Yes	Yes	Yes	No	No	No
2	Yes	Yes	No	Yes	No	No
3	Yes	No	Yes	Yes	No	No
4	Yes	Yes	No	No	Yes	No
5	Yes	No	Yes	No	Yes	No
6	Yes	No	No	Yes	Yes	No

The first thing to notice is that iteration 1 and 6 are trivial, in this case there is a common suit between all the Yes's which means we can safely pick that suit (in 1's case it is Hearts, in 6's case it is Spades). The second thing to notice is 3 and 4 are also solvable because the Yes's both share the common suits and have inconsistencies. For example in 3's case there are two yes cases that contain hearts, 2 yes cases that contain Spades and 1 yes case containing a clubs and 1 yes case containing a diamonds. We can safely say that clubs are diamonds are not the suits the Tester has, so we can easily solve this problem.

The trouble occurs in iteration 2 and iteration 5, the issue is there is no way to distinguish between each iteration. In this case all we are able to do is exclude a suit, in the case of iteration 2 we can safely confirms diamonds is definitely NOT a suit and in iteration 5 we can safely confirm clubs is NOT a suit. But in this case we have three suit contenders and there's no information about which suit is the correct one.

For iteration 2 for example we know that the Tester has a hearts, spades OR a clubs, we know that out of these three the Tester has two of them that's all we can confirm. He's only given us all Yes's for any combination containing any of these 3 suits. We've effectively moved the problem into a three suit problem and this three suit problem is unsolvable, because if you guess any two of three suits you'll always get a yes, so you can just say yes all the time.

Currently I don't believe there's a way to minimize this problem which means the final answer is:

Yes the Tester can always (granted he picks up two different suits) make it impossible for the Guesser to get it right