# Does this game terminate?

Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"):

Two players randomly split in two decks a standard deck of cards. Each player gets one deck.

The players alternate placing down in a stack the next card from their deck.

If a player (A) places down a special card, i.e. a I, II, or III, the other player (B) has to place down consecutively the corresponding number of cards.

• If in doing so B places down a special card, the action reverses, and so on; otherwise, if B places down the corresponding number of cards but no special card, A collects all the cards that were put down and adds them to their deck. A then restarts the game by placing down a card.

The first player to run out of cards loses the game.

Note: The outcome of the game depends exclusively on the initial partition of the deck. (Which may make this game look a bit pointless ;-)

Question: Does this game always terminate? What if we generalize this game and give any two sequences of cards to each player?

• A similar game is Beggar-My-Neighbour; played with a deck of 52 cards (A,J,Q,K are the penalties). It is also known as Strip Jack Naked or Beat Your Neighbor Out of Doors and according to Wikipedia it is an open problem whether a non-terminating game exists or not. – Marzio De Biasi Apr 17 '14 at 22:58
• (since its long open sounds like a tcs.se question to me.) conway suggests in the 1st page of that ref to try computer searches. has anyone? it seems a good strategy would be to try small decks & exhaustively answer the question and increase deck size. if its always terminating for small decks it seems likely true for arbitrary size decks (and maybe an inductive proof could be created this way). a related question, are there any card games at all that have been proven sometimes nonterminating? presumably they are quite rare because most games are based on someone eventually winning! – vzn Apr 18 '14 at 2:54
• @MarzioDeBiasi thanks for the link, it is the same game. I don't see undecidability because given two finite decks whether the game terminates is obviously decidable. – Manu Apr 18 '14 at 14:24
• @EmanueleViola: you're right, if the same deck configuration appears two times the game will never end! I deleted the comment. – Marzio De Biasi Apr 18 '14 at 14:38
• This is Egyptian Rat Screw, but without the slapping! – argentpepper Apr 18 '14 at 18:04

# Regarding Beggar-My-Neighbour

Paulhus (1, p.164) wrote in 1999:

If $C$ is a full deck of cards, does ${D_{2}}^{'}(C)$ have a cycle? We leave this question unanswered except to say that we have been unable to find one in 3.2 billion randomly chosen deals.

But Conway et al. (2, p.892) wrote in 2006:

Strip-Jack-Naked, or Beggar-My-Neighbour **1

Another problem that took almost 47 years to solve concerns this old children’s game. Each of the two players starts with about half of the cards (held face-down), which they alternately turn over onto a face-upwards “stack” on the table, until one of them (who's now “the commander”) first deals one of the “commanding cards” (Jack, Queen, King, or Ace).

After one of these has been dealt, the other player (now “the responder”) turns over cards continuously until EITHER. **2 a new commanding card appears (when the players change roles **3) or respectively 1, 2, 3, or 4 non-commanding cards have been turned over. In the latter case, the commander turns over the stack and ajoins it to the bottom of his hand. The responder then starts the formation of a new stack by turning over his next card, and play continues as before.

A player who acquires all the cards is the winner and in real games, it seems that someone always does win. The interesting mathematical question, posed by one of us many years ago, was “is it really true that the game always ends?” Marc Paulhus has recently found the answer to be “no!”. About 1 in 150,000 games (played with the usual 52 cards) goes on forever.

We are fairly confident that no one person has played the game anything like that number of times, so the chance (with random shuffling) of experiencing a non-terminating game in a lifetime’s play must be very small indeed.

Just as surely, however, the total number of times this game has been played by the World’s **4 children must be significantly larger than 150,000, so many of them will have been theoretically non-terminating ones. We imagine, though, that in practice most of them actually did terminate because someone made a mistake.

Unfortunately I was not able to found in (2) any reference to the discovery of Paulhus... I would love to see a sequence of cards that gives a non-terminating game in order to say that the problem is solved.

In 2013, Lakshtanov and Aleksenko (3) wrote:

For card games of the Beggar-My-Neighbor type, we prove finiteness of the mathematical expectation of the game duration under the conditions that a player to play the first card is chosen randomly and that cards in a pile are shuffled before being placed to the deck. The result is also valid for general-type modifications of the game rules. In other words, we show that the graph of the Markov chain for the Beggar-My-Neighbor game is absorbing; i.e., from any vertex there is at least one path leading to the end of the game.

but their rules are not the ones I followed when I played the game when I was a child ;-)

To the best of my knowledge the longest Beggar-my-Neighbour game was found in 2014 by William Rucklidge with 7960 cards:

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK


# Regarding Cavacamicia

I usually played it with a 40 cards deck, simulations with an half deck (only 20 cards) gives 16 non terminating games on a total of 3.448.400 games.

# Bibliography

(1) PAULHUS, Marc M. Beggar my neighbour. American Mathematical Monthly, 1999, 162-165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R.; CONWAY, John H.; GUY, Richard K. Winning Ways for Your Mathematical Plays, Volume 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays-volume-4

(3) LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finiteness in the Beggar-My-Neighbor card game. Problems of Information Transmission, 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051