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!