# Flawless war his week’s Riddler Classic has to do with the card game “War”. Here is the problem, paraphrased:

War is a two-player game in which a standard deck of cards is first shuffled and then divided into two piles with 26 cards each; one pile for each player. In every turn of the game, both players flip over and reveal the top card of their deck. The player whose card has a higher rank wins the turn and places both cards on the bottom of their pile. Assuming a deck is randomly shuffled before every game, how many games of War would you expect to play until you had a game that lasted just 26 turns (with no ties; a flawless victory)?

Here is my solution:
[Show Solution]

## 8 thoughts on “Flawless war”

1. Bob Jenkins says:

Minor quibble.

This appears to be calculated as a one sided probability (winning all hands). As I read the Riddler for this week, losing all hands is also a 26 turn game. So, do you need to multiply the probability you found by 2? (I am wondering how long it will be until I see a 26 turn game, not how long it will be to see myself get a 26 turn game).

Thanks again for all of your wonderful write-ups! Clear illustration of what’s going on every time!

1. Laurent says:

That is correct. To compute the probability that the game will last 26 turns with no wars, you would simply multiply my result by 2. The problem statement talks about a person claiming that they won a flawless game. So I wanted to assess the probability of that exact event occurring. i.e. how many games would that person have to play before they had a flawless win. I did not want to include the events where they would lose to an opponent that won flawlessly.

2. Ryan Hansen says:

Nice write up of a complicated problem. With regard to the number of games before the probability hits 50% or 95%, you can use the approximation that 1 – 1/x = e^(-1/x) as another way to calculate these with less computation. Using the 50% prob, you solve for (1-1/x)^n = 0.5. Using the approximation, you could say (1-1/x)^n = (e^(-1/x))^n = e^(-n/x) = 0.5.

After some rearranging, you get n = -ln(0.50)*319,240,361 = 221,280,556.

For the 95% case, you could set n = -ln(0.05) * 319,240,361 = 956,358,653.

3. Evan Vogelbaum says:

Great write up! I have a bit of trouble understanding the second observation of the rearrangement of f… although the coefficients are symmetric, the actual functions seem not to be… i.e. f(3, 2, 1) results in 3*f(2, 2, 0) + 2*f(3, 1, 0) + 6*f(1, 2, 1) while f(1, 2, 3) results in 3*f(0, 2, 2) + 6*f(1, 1, 2) + 2*f(0, 1, 3). It does not seem obvious to me that these two expressions should be equal, so I feel I must be missing something. Are you able to help me out?

1. Laurent says:

Let’s use your example of a 6-card deck and say we want to show that $f(3,2,1) = f(1,2,3)$. The coefficients multiplying the $f$’s after we decompose each side are 3, 2, 6. Matching up the terms on both sides with equal coefficients, the equality will be true so long as $f(2,1,1) = f(1,1,2)$ and $f(2,2,0) = f(0,2,2)$ and $f(3,1,0) = f(0,1,3)$. Note that these three equalities all involve 4-card decks.

More generally, any $f(\ldots)$ for an $m$-card deck will decompose into a sum of terms involving $(m-2)$-card decks. We can continue recursively matching coefficients as far as possible, and we will end up with a bunch of terms that have all cards of the same type, e.g. $f(0,4,0,0,0)$ or $f(0,0,2,0)$, in which case the answer is zero (if the deck looks like that, games will always end in ties, not wins), or a term with no cards in the deck at all, e.g. $f(0,0,0)$, in which case the answer is 1.

More formally, you can prove the rearrangement property by using induction. First by showing that it holds for all 0-card decks (trivial), then all 2-card decks, then all 4-card decks, etc. When you get to $m$, applying the recursion reduces to the $m-2$ case, which you’ve already shown.

4. S Kumar says:

Something looks wrong! I tried it with n = 3 and m = 4.

I tried the simulation with 12 cards, n = 3 and 4 suits. Result is 2,903,040 wins over 12! = 479,001,600 games.
The answer by the above program is 1,244,160.
===========================================================================

import math

win = 0
tot = 0
NUM_SUITS = 4

for i1 in range(12):

for i2 in range((int(i1/NUM_SUITS) - 1) * NUM_SUITS):
if i2 == i1: continue

for i3 in range(12):
if i3 in (i1, i2): continue

for i4 in range((int(i3/NUM_SUITS) - 1) * NUM_SUITS):
if i4 in (i1, i2, i3): continue

for i5 in range(12):
if i5 in (i1, i2, i3, i4): continue

for i6 in range((int(i5/NUM_SUITS) - 1) * NUM_SUITS):
if i6 in (i1, i2, i3, i4, i5): continue

for i7 in range(12):
if i7 in (i1, i2, i3, i4, i5, i6): continue

for i8 in range((int(i7/NUM_SUITS) - 1) * NUM_SUITS):
if i8 in (i1, i2, i3, i4, i5, i6, i7): continue

for i9 in range(12):
if i9 in (i1, i2, i3, i4, i5, i6, i7, i8): continue

for i10 in range((int(i9/NUM_SUITS) - 1) * NUM_SUITS):
if i10 in (i1, i2, i3, i4, i5, i6, i7, i8, i9): continue

if int(i9/NUM_SUITS) > int(i10/NUM_SUITS): win += 1

for i11 in range(12):
if i11 in (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10): continue

for i12 in range((int(i11/NUM_SUITS) - 1) * NUM_SUITS):
if i10 in (i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11): continue

win += 1

print(win, math.factorial(12))

1. Laurent says:

Hi S Kumar,

I reformatted your post because the tabs got lost and they’re rather important!
In any case, I tried running your code and I get win==0. Did I make a mistake in where I put the tabs?
If you want to preserve tab structure, post your code inside of a “pre” tag, i.e.

<pre>
(code goes here)
</pre>

5. Evan Vogelbaum says:

Thank makes a lot of sense! Thank you very much.