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. 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. 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. 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. 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. 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. 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. 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>
      

Leave a Reply

Your email address will not be published. Required fields are marked *