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.
JohnDiscardedMatt
13 pairs0 pairs13 pairs
12 pairs2 pairs12 pairs
11 pairs4 pairs11 pairs
10 pairs6 pairs10 pairs
9 pairs8 pairs9 pairs
8 pairs10 pairs8 pairs
7 pairs12 pairs7 pairs
6 pairs14 pairs6 pairs
5 pairs16 pairs5 pairs
4 pairs18 pairs4 pairs
3 pairs20 pairs3 pairs
2 pairs22 pairs2 pairs
1 pair24 pairs1 pair
0 pairs26 pairs0 pairs
So we see that in any case, there is a tie between John and Matt. So Matt never ends up with a dollar.

Comments

Post a Comment

Popular posts from this blog

Pick a Random Byte

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After pick
Read more

The Fox and The Duck

Question:  A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground? Answer:  One would think that the duck could swim directly away from the fox. So the duck would have to swim a distance r. The fox would have to cover half the circumference of the pond (pi * r). Since the fox is four times faster than the duck, we know that (pi * r) < (4 * r) This would make it seem like it is impossible for the duck to escape. So how could the duck make life most difficult for the fox? If the duck just tries to swim along a radius, the fox could just sit along that radius and the duck would continue to be trapped. The duck could swim in concentric c
Read more

First Non-Repeated Character

Question:  Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer:  Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. char returnFirstNonRepeatedChar( char * str ) { int i, repeated = 0; int len = strlen(str); for( i = 0; i < len; i++ ) { repeated = 0; for( j = 0; j < len; j++ ) { if( i != j && str[i] == str[j] ) { repeated = 1; break; } } if( repeated == 0 ) { // Found the first non-repeated character return str[i]; } } return ''; } This approach seems to work perfectly well. But
Read more