Betting on cards

A deck consisting of $n$ red cards and $n$ black cards are shuffled. The cards are then flipped one at a time. Before each flip, you are allowed to make a bet on the color of the next card. If you guessed right, you win an amount equals to your bet. If you guessed wrong, you lose your bet. You don't have to bet on every flip, in fact you don't have to bet at all if you so wish. The bets can be any amount of real number, and you start with one dollar.

You decide to employ the following strategy. Suppose that, by counting already-flipped cards, you deduce that there are $R$ red cards and $B$ black cards left in the deck. If $R > B$, you guess red while betting $\frac{R-B}{R+B}$ of your total money. Similarly if $R < B$ you guess black while betting $\frac{B-R}{B+R}$ of your total money. If $R=B$ you don't bet that turn. Show that this strategy guarantees a final amount of: $$\frac{2^{2n}n!n!}{(2n)!}$$ Note: this final amount is much bigger than people think. That sum equals to: $$\left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$ which is already greater than 2, and only increases as $n$ increases. This is an extension to the obvious strategy to wait until the last card before we bet the one dollar that we start with, to which we'd be guaranteed a final amount of two.

First Solution

First we claim the following: if at any point there are $R$ red cards and $B$ black cards left in the deck, and your current total is $x$, employing the above strategy will give you a final amount of: $$\frac{2^{R+B}R!B!}{(R+B)!} x$$ That claim is easily verified if either $R+B=1$ because then we would know exactly what's left in the deck. Now we prove the claim by induction on $R+B$. Clearly if $R=B$ then we don't bet that flip, and we reduced it to the case $R+B-1$. But if $R \neq B$, and WLOG we may assume that $R > B$. We bet $\frac{R-B}{W+B}$ that the next card will be red.

Case 1: the next card is red. That means our current total becomes $(1 + \frac{R-B}{R+B})x = \frac{2R}{R+B}x$. But the deck now contains $R-1$ red and $B$ black, so by our induction hypothesis, our final amount will be: $$\frac{2^{R+B-1}(R-1)!B!}{(R+B-1)!} \frac{2R}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$

Case 2: the next card is black and we lost our bet. That means our current total is now $(1 - \frac{R-B}{R+B})x = \frac{2B}{R+B}x$ and the deck contains $R$ red and $B-1$ black, so our final amount is: $$\frac{2^{R+B-1}R!(B-1)!}{(R+B-1)!} \frac{2B}{R+B}x =\frac{2^{R+B}R!B!}{(R+B)!} x $$ And the claim is proven. Now it's straightforward to apply that if $R=B=n$, we have: $$\frac{2^{2n}n!n!}{(2n)!} = \frac{(2n)(2n-2)\dots (4)(2)}{(2n-1)(2n-3) \dots (3) (1)}$$ $$= \left(1 + \frac{1}{2n-1} \right) \left(1 + \frac{1}{2n-3} \right) \dots \left(1 + \frac{1}{3} \right) \left(1 + \frac{1}{1} \right)$$

Magician and cards

From IMO 2000, problem 4:

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card. A member of the audience draws two cards from two different boxes and announces the sum of numbers on those cards. Given this information, the magician locates the box from which no card has been drawn.

How many ways are there to put the cards in the three boxes so that the trick works?

Solution

There are 12 possible ways to divide the card:
1. RWWW...WWWB (Card 1 goes to red box, card 2 to 99 go to white box, and card 100 goes to blue box) and all of its permutations, for a total of 6 ways.
2. RWBRWBRWB... and all of its permutations, for a total of 6 ways.

We now show that there are no other ways to put the cards. Consider the placement string (RWB string as in the example above). We will divide into two major cases: those with repeating characters, and those without repeating characters.

First, note that if there is a substring "RW" anywhere in the string, we don't allow substring "RB," for otherwise we can have an ambiguous sum of W+R versus R+B. Likewise, if there is a substring "RW" then we don't allow "BW."

Now, suppose there is a repeating substring "WW." Then we can't have a "RB" or "BR" anywhere in the string because there would be an ambiguous sum of R+W versus B+W.

Note that if we already have a "WW" then we can't have a "BB" because "BB" would mean that no "RW" or "WR" can exist, but we already established that no "RB" or "BR" can exist. So combination of "WW" and "BB" altogether would make it impossible for any "R" to exist in the string, a contradiction.

Consider the last B in the string, and call this B'. There are 4 possibilities of strings that come after B':
1. B'B: contradiction because B' is the last B in the string
2. B'R: contradiction because no BR is allowed
3. B'W
4. B' is the last letter in the whole string.

Consider also the last R in the string, call it R'. As in B', we only have 2 possibilities of strings that come after R':
5. R'W
6. R' is the last letter in the whole string.

Now obviously 4 and 6 cannot both be true, so one of them (possibly both) must be false. WLOG, we can assume that 6 is false, then 5 has to be true. If there's RW, we cannot have BW, so 3 is false, which means 4 is true.

So the last R in the string is followed by a W, and B is the last letter in the whole string. Since there already is an RW, we can't have a BW in the entire string. Also, we can't have BB, or BR, so there's no other place for another B. That means B' is the last and only B in the string.

Now, R' can't be preceded by another R (because no RR is allowed), nor by a B (because no BR is allowed), nor by a W, because a WR and a WB' can't both exist. So R' is the earliest R in the string. Since it's also the last, then R' is the only R in the string.

So we have RWW...WWB (and all of its permutations) as the only solution that allows repetition between characters.

Now, suppose there's no repeated characters. We assert that we cannot have a pattern like "RWR" anywhere in the string. Because the character that comes after "RWR" cannot be B, because "RWRB" gives an ambiguous sum of R+B and W+R. We also cannot have RWRR for there's no repeating characters. So we must have either "RWRW" or the fact that RWR is the ending of the entire string. If it is the ending, then we apply the same argument forward, and conclude that the ending must be WRWR. Either way, an RWR can be extended to RWRW or WRWR. But since there is at least one B in the string, and this B cannot be adjacent to another B, and we can't have BW, WB, BR, or RB either, a contradiction. So there must not be any RWR or its permutations anywhere in the string.

Suppose card 1 goes to R, and card 2 goes to W. Card 3 can go to:
1. R, forming RWR, contradiction
2. W, forming a WW, contradiction
3. B.

So we have RWB as the beginning of the string. Now card 4 can go to:
1. R
2. W, forming a WBW, contradiction
3. B, forming a WBB, contradiction.
So card 4 must go to R.

We can continue this argument inductively to arrive that the entire string must have the form: RWBRWBRWB....

Shuffling Card

A deck of 31 cards is being shuffled, where at each point, the shuffler may perform the following operation:

1. Cut the deck in half and interleave each half to perform a new deck. The cards at position 1,2,3,...,15 now occupy position 2,4,6,...,30, and the cards at position 16,..., 31 now occupy position 1,3,...,31.

2. Similar to operation one, but with different "cut." The cards at position 1,2,3,...,16 now occupy position 1,3,5,...,31, and the cards at position 17,...,31 now occupy position 2,4,6,...,30.

3. Take $m$ cards from the top and move them to the bottom of the deck (a standard cut).

Starting from the original configuration, how many different configurations can be achieved by repeating the three operations above?

Solution

There are $5.31 = 155$ different configurations.
First, it's clear that the deck can be "rotated" in any amount along one direction, so we only consider rotational configurations.
Step 1 moves cards from position $m$ to $2m \mod 31$
Step 2 moves cards from position $m$ to $2m-1 \mod 31$
Step 3 moves cards from position $m$ to $m+k \mod 31$ for some $k$.

Now, step 3 does not change the rotational configurations. Step 1 and 2 both can be consolidated into the move from $m$ to $2m \mod 31$ and followed by a suitable number of step 3.

Thus, the number of different rotational configurations are the smallest number $n$ such that $2^n \equiv 1 \mod 31$, and that means $n=5$.

So there are 5 rotational configurations and 31 configurations within each rotational configuration, for a total of 155.

Paired cards

A standard deck of 52 cards is shuffled with uniform probability. A "pair" is defined as two numerically identical cards that are adjacent in the stack. What is the probability that the deck contains no pair?

Challenge: Find the probability that the deck contains exactly $n$ pair for $n=1,2,\cdots,26$.