# A coding theory/probability puzzle

I thought of the following problem and I am stuck in solving it.

Suppose there is a deck of 4 cards with 2 red and 2 blue. I pick 2 cards at random and choose 1 and show the other to my friend. With what probability can my friend find the color of my card if we have agreed on a good strategy in advance?

If my friend always guesses the color red, we only fail in this game if I get 2 blue cards. That happens with probability 1/4 and it is the best I can achieve in this case.

However, if the cards are numbered we can do even better, i.e. there is red card 1 and red card 2, blue card 1 and blue card 2. In this case, we can agree that my friend chooses the color of the card I gave him if the number is 1 and flips the color if it is 2. You can check that the only way we can fail is if I get both the red and the blue card of 1. (If I get both cards of the same color I show him the number 1 card. If I get two cards of different colors I show him the number 2 card and we win.) Since the probability of drawing two cards with the number 1 is 1/6, having numbers on the cards clearly helps.

My question is what happens when there are $$N$$ cards of $$N$$ colors ($$N^2$$ in total) and I draw $$N$$ cards, choose 1 and reveal $$N-1$$ cards to my friend (in a random order, i.e. the order cannot encode information). What is the strategy that maximizes our probability of winning? How does this differ if cards are numbered or if they are not?

I am interested both in optimal strategies for small $$N$$, or with asymptotic bounds for large $$N$$ in both the numbered and unnumbered cases. Could it be that the probability in the numbered case goes to 1 and the unnumbered case is small? This would be very unintuitive!

• I like this question although it seems like a lot of work to solve it. Have you tried some strategies for general $N$? – Stan Tendijck Mar 7 at 14:19
• The probability of drawing both blue cards is $\frac{1}{6}$, not $\frac{1}{4}$ – Daniel Mathias Mar 7 at 14:42
• Having the numbers does not help in your two card case. You win $\frac 56$ both ways. – Ross Millikan Mar 7 at 16:36
• From what I've seen, if you cannot preset the order of revealed cards, the best strategy for N=3 is also to preset what color should be guessed. If you can control the order of reveal, then it is possible to be correct for any possible hand except for one – Moko19 Apr 2 at 16:58