{"id":2939,"date":"2020-08-28T14:08:58","date_gmt":"2020-08-28T19:08:58","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2939"},"modified":"2020-08-28T17:25:10","modified_gmt":"2020-08-28T22:25:10","slug":"flawless-war","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/flawless-war\/","title":{"rendered":"Flawless war"},"content":{"rendered":"

his week’s Riddler Classic<\/a> has to do with the card game “War”. Here is the problem, paraphrased:<\/p>\n

\nWar 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)?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

Suppose our cards have values $\\{1,2,\\dots,n\\}$ and the deck contains $m_i$ cards with value $i$. The total number of cards in the deck is equal to $m = m_1 +\\dots+m_n$, and we assume $m$ is even so that the deck can be evenly split in half. In a standard deck of playing cards, we have $n=13$ and $m_1=m_2=\\dots=m_n = 4$.<\/p>\n

Rather than thinking about “how many games we would expect to play before I had a flawless game”, let’s instead work out the probability that a game of War will be flawless for me (I wins in $m\/2$ turns with no ties). This is a counting problem: how many ways are there of arranging the cards in the deck so that I win flawlessly?<\/p>\n

To this effect, define $f(m_1,\\dots,m_n)$ to be the number of ways I can win flawlessly if the cards remaining have distribution $(m_1,\\dots,m_n)$. We will develop a recursive formulation of $f$.<\/p>\n

If I pick “$i$” in the first round, I will win the round with no tie if my opponent picks “$j$” with $j \\lt i$. This can happen in $m_i m_j$ ways, and then I can win the remaining rounds flawlessly in $f(\\dots)$ ways, where the arguments $m_i$ and $m_j$ are each decremented by $1$. Therefore, we can write:
\n\\[
\nf(m_1,\\dots,m_n) = \\sum_{1 \\leq j \\lt i \\leq n} m_i m_j f(m_1,\\dots,m_j-1,\\dots,m_i-1,\\dots,m_n)
\n\\]We also have the terminal condition $f(0,\\dots,0)=1$, for if we ever achieve this condition, there are no cards left and we have won!<\/p>\n

We can make two critical observations that will greatly simplify computation of $f$:<\/p>\n