Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules.

A standard $52$ card deck is shuffled and dealt evenly to two players face down. Every turn, both players lay down their top cards (a "battle"). The higher card wins, and the winning player gets both cards and places them at the bottom of his deck. If the battle is a tie, a "war" is declared, and each player lays down his next three cards. Of these six cards, the owner of the card with the highest value wins the turn, and all cards played that turn are placed at the bottom of his deck. If a player does not have $3$ cards to play in a war, he wins the turn by default. If the war is a tie, another war is held ("double war"), and so on until one of the players wins. The game ends when a player runs out of cards.

If the case occurs that the deals are entirely symmetric, e.g. both players decks are two two's, two threes, two fours, etc. in that order, we say that both players lose, as does everyone watching. (In other words, the game "fails.") This would be considered a finite game.

Ordering Conventions.

To consider the game from a mathematical standpoint, the order that cards are placed into a player's hand after he wins a turn must be well-defined. There are many choices to be made here, especially considering that we can vary the conventions for double wars, triple wars, etc., which is where the most potential for variation lies. For the sake of simplicity, and because it coincides with how I pick the cards up when I am actually playing, I suggest that when a player wins a turn, he picks up all of the losing cards in the order that they were laid down (highest to lowest), followed all of the winning cards.

For example, say a turn begins with a battle in which players $\sf X$ and $\sf Y$ both lay down aces. Thus a war begins. Say that player $\sf X$ lays down a Jack, a King, and a $3$, in that order, and player $\sf Y$ lays down a Queen, a $4$, and a King, in that order. So a double war is held. Player $\sf X$ lays down $5$, $6$, $7$ and player $\sf Y$ lays down $8$, $9$, $10$. Now, player $\sf Y$ wins, so all of these cards are placed in his deck, ordered as such:

$$\sf (\ldots\text{previous deck}\ldots, \underbrace{\overbrace{\text{A},}^{\text{battle}}\overbrace{\text{J},\text{K},3,}^{\text{first war}}\overbrace{5,6,7,}^{\text{second war}}}_{\text{losing cards}}\underbrace{\overbrace{\text{A},}^{\text{battle}}\overbrace{\text{Q},4,\text{K},}^{\text{first war}}\overbrace{8,9,10}^{\text{second war}}}_{\text{winning cards}}).$$

A possible variation would be to pick up the cards in each war separately, in the order the wars were played, in which case the above example would yield

$$\sf (\ldots\text{previous deck}\ldots,\overbrace{\underbrace{A,}_{\text{losing}}\underbrace{A,}_{\text{winning}}}^{battle}\overbrace{\underbrace{J,K,3,}_{\text{losing}}\underbrace{Q,4,K,}_{\text{winning}}}^{\text{first war}}\overbrace{\underbrace{5,6,7,}_{\text{losing}}\underbrace{8,9,10}_{\text{winning}}}^{\text{second war}}).$$

Questions.

First and foremost,

Is War necessarily finite?

Perhaps there exists some arrangement of starting decks which would produce an everlasting game, forever permuting cards between the two players. If this is not possible, can we prove it? Which ordering conventions always give rise to finite games (if any exist)?

and, for bonus points,

There are $\rm {52 \choose 26}(26!)^2\approx 10^{41}$ possible ways to deal the decks at the beginning of the game. Since suits are irrelevant, however, some arrangements will result in identical games. What is the expression for the number non-identical games? Thanks joriki.

A (substantially) tougher question: if we say that two games are similar if every turn has the same outcome, what is the expression for the number of non-similar games?

share|improve this question
2  
2  
On the bonus question: $\binom{52}{26}(26!)^2=52!\approx8\cdot10^{67}$. The number of non-identical games is obtained by dividing through the permutations of the thirteen ranks: $52!/(4!)^{13}\approx9\cdot10^{49}$. –  joriki Nov 7 '12 at 6:05
    
Thanks for the links @GerryMyerson. I should note that my suggested ordering convention is opposite what these other posts are doing (deliberately so, as I'd seen the $K,A$/$A,K$ example in the first link). In particular, I'm interested in knowing whether a periodic example like this can be constructed for any ordering convention. –  Alexander Gruber Nov 7 '12 at 6:06
1  
I have a puzzle book that have a variant of this game (2 suits of 5 cards, in a war you play one card instead of 3, you order the cards such that the war cards come first, then the winning card then the losing card). It asks the question "from how many moves can you be sure that the game will go on indefinitely ?", and its answer is 40, suggesting that infinite games DO arise (if they don't, while the question and answer could still be technically correct, that would be really shrewed) –  mercio Nov 9 '12 at 15:20
1  
Infinie games exist. See: mathoverflow.net/questions/11503/… –  Potato Dec 25 '12 at 7:32

1 Answer 1

up vote 14 down vote accepted
+50

A few years ago I studied this problem in the case in which there is only one suit in an $n$-card deck, so that the cards have a strict ranking from $1$ to $n$ and wars are not possible. I thought it would be easier to understand this simpler case before tackling decks with four suits in which wars are possible. As it turns out, I found even this case to be sufficiently difficult.

Under the convention that the losing card is picked up first, I found a way to construct cycles (so infinite games) for all values of $n$ except when $n = 2^k$ for some $k$. Under the convention that the winning card is picked up first, I found a way to construct cycles for all values of $n$ except when $n = 2^k$ or $n=3 \cdot 2^k$ for some $k$. Since $52 = 13 \cdot 2^2$, my constructions show how the 52-card deck with a strict ordering of the cards can exhibit cycling under either ordering convention.

Again, this is what I found for a simpler version of War than the OP is asking about, but perhaps this sheds some light on the more general case. Obviously the possibility of wars makes the problem much more difficult. I've wondered, though, if the method I found for generating cycles in the one-suit case could be modified to generate cycles when there is more than one suit. I worked on that question a little but didn't get very far.

(The paper is "Cycles in War," Integers 10: Article G2, 747-764, 2010, and can be found near the bottom of this page. The paper focuses on the "winning card is picked up first" convention, but I discuss the "losing card is picked up first" convention in the final section. I should also mention that I answered the question in the second of Gerry Myerson's links with a reference to this paper.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.