3
$\begingroup$

I have a question that needs a response using graph theory but I can't think of a method how to use a graph on that. Tha problem is ->

Two friends perform the following game card: the first choses at random six cards from a regular deck (of 52 cards), looks at them, keeps one of them, and arrange the other five in order from left to right, face up; the, the second correctly guesses the sixth card. Prove that the two friends can agree on a system which always makes this possible, and find such a system.

I have a feeling that this is a graph matching problem but don't know where to go from here.

$\endgroup$
1
  • $\begingroup$ There are $5!=120$ different ways to order the the five cards, and only $47$ remaining cards to encode. So this shouldn’t be hard, but picking an encoding an enumerating it is dull. $\endgroup$
    – Thomas Andrews
    Commented Nov 19, 2020 at 18:45

1 Answer 1

Reset to default
1
$\begingroup$

Here's an easy way to do it:

First rank the cards from $1$ to $52$ however you like (standard would be $2\clubsuit=1$ to $A\spadesuit=52$ but it isn't important).

As there are $>4$ cards we must have some duplicated suit. Choose the special card as one from the duplicate suits. Doesn't matter if you have more than one duplicated suit, nor if you have more than two cards in that suit. It will matter which card you choose to hide from the duplicated suit, we'll come to that later.

Place a card of the duplicate suit first. Now you know what suit the missing card has. Note that there are only $12$ possible cards for the missing one.

There are $6$ permutations for the other three (viewing them as Low, Middle, High). Thus the order in which they are placed determines a number from $1$ to $6$. You can number the permutations however you like.

Viewing the duplicate suit cyclicly, add that number to the card on the far left. Thus if you have a $6\diamondsuit$ on the far left and the permutation is number $4$ then the answer is $10\diamondsuit$. If the far left card is $K\heartsuit$ then the answer is $4\heartsuit$ and so on).

The key point is that of the two cards in the same suit one of them must be $≤6$ away from the other, that tells you which one of the two to hide.

$\endgroup$

You must log in to answer this question.