# Card Pairology?

Question: John and Matt decide to play a game using a deck of cards. The game involves flipping two cards at a time. If both cards are black, they go into John’s pile and if both cards are red, they go into Matt’s pile. If one card is red and one card is black, they go into a discard pile. The game is played until all 52 cards have been flipped. The person with the most cards in their pile wins. If there is a tie, John wins. If Matt has more cards than John, then John pays Matt a dollar. What is the chance of Matt getting a dollar?

Answer: Any guesses? The chance of Matt getting any money is zero. Do you know why?

Say the deck is arranged in a way such that there are 13 black pairs. In this situation, John gets 13 black pairs. And since there are no other black cards left, Matt gets 13 red pairs too. So there’s a tie and John wins.

Suppose there are 12 black pairs in the deck. In this case, there would be 2 black cards left in the deck that would pair up with 2 other red cards in the deck. These 2 black cards would never be together since we have already claimed that there are only 12 black pairs in the deck. As a result, 2 pairs of cards end up in the discard pile. The remaining cards would all be red and Matt would get 12 red pairs too. So once again, there’s a tie and John wins.

We could continue this process through induction. Assuming there are 11 black pairs, there would be 4 other black cards that pair up with 4 other red cards and go into the discard pile. Once again, both John and Matt end up with 11 pairs of cards each and John wins.

Here’s a table to explain each case.

 John Discarded Matt 13 pairs 0 pairs 13 pairs 12 pairs 2 pairs 12 pairs 11 pairs 4 pairs 11 pairs 10 pairs 6 pairs 10 pairs 9 pairs 8 pairs 9 pairs 8 pairs 10 pairs 8 pairs 7 pairs 12 pairs 7 pairs 6 pairs 14 pairs 6 pairs 5 pairs 16 pairs 5 pairs 4 pairs 18 pairs 4 pairs 3 pairs 20 pairs 3 pairs 2 pairs 22 pairs 2 pairs 1 pair 24 pairs 1 pair 0 pairs 26 pairs 0 pairs

So we see that in any case, there is a tie between John and Matt. So Matt never ends up with a dollar.

Liked this post? Spread the word on Twitter and Facebook 🙂

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

## 4 Responses

1. manful says:

Like you can nver win in casino.

2. Candy says:

For each pair of black cards, there’s a pair of red cards left that will eventually land with Matt, and vice-versa. If there’s one red one black, it will affect both players as this pair will land in the discard pile. So in the end there will be a tie, which according to the rules, John will win anyways.
No chance for poor Matt to make a buck 🙂

3. karthika says:

fantastic job

4. There is no need to create a table. The pigeonhole principle summarizes the whole solution in one fell swoop. Like so:

Assume that Matt gets at least X pairs of red cards. Then, in the rest of the deck there are 26-2*X red cards and 26 black cards. By the pigeonhole principle, after the remaining red cards are paired off, there must be at least 2*X black cards remaining, which must be paired with one another, thus giving John at least X pairs of black cards. Since this holds for any X, we can see that Matt can never beat John.

XHTML: These are some of the tags you can use: `<a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>`