17
$\begingroup$

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?

$\endgroup$
6
  • 5
    $\begingroup$ 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. $\endgroup$ Apr 17, 2014 at 22:58
  • $\begingroup$ (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! $\endgroup$
    – vzn
    Apr 18, 2014 at 2:54
  • $\begingroup$ @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. $\endgroup$
    – Manu
    Apr 18, 2014 at 14:24
  • $\begingroup$ @EmanueleViola: you're right, if the same deck configuration appears two times the game will never end! I deleted the comment. $\endgroup$ Apr 18, 2014 at 14:38
  • 1
    $\begingroup$ This is Egyptian Rat Screw, but without the slapping! $\endgroup$ Apr 18, 2014 at 18:04

2 Answers 2

11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Interesting... if Conway's statement is true, then one should be able to simulate a couple million random games and almost surely find a cycling game. If none is found, then Conway's statement is likely mistaken. $\endgroup$
    – Kevin Wang
    Mar 14, 2023 at 20:52
5
$\begingroup$

Digression

Maybe since the time of asking you found the answer yourself... However yes, "Cavacamicia" has cycles so sometimes it is non terminating.

Some friends and I found this back in May 2016. At the time we were beaten by just some days by Michele Cocco Lasta who found the first cycle before us. He didn't whant to publish the configutation for "not taking away the pleasure of search to other people". He just published a one line note on a facebook page he had named "Cavacamisa Straccia camicia Pelagalletto Infinita".

Recently I was noticed that on other sites someone found the configurations believing to be the first one. Maybe someone found it before 2016 too.

Since then I moved to try tackling Beggar My Neighbour building a distributed computing network (with few PC actually) and looking for math reasonings that can help to reduce the search space.

Answer

The following are some of the existing starting sequences that generates non terminating games. All of these are related to three distinct cycles.

Only Cycle 3 has balanced configurations in it (with 20/20 cards) while Cycle 1 and Cycle 2 can be reached from the given starting configurations but do not contain balanced configurations directly.

The search was not exaustive so I cannot say if there are other cycles on Cavacamicia.

Cycle 1 - 18 rounds, 93 tricks
00200000021000013000 | 00020001020310030300
00002000102031003030 | 00200000021000013000
00001000320020010001 | 32020000000010030003
02001000121003000200 | 01003000303000020000
00100300030300002000 | 02001000121003000200
01000100300020001020 | 03303000020000002100
00330300002000000210 | 01000100300020001020

Cycle 2 - 10 rounds, 78 tricks
00000030100202020310 | 00010000300002100300
00001000030000210030 | 00000030100202020310
10020202031000030030 | 00002100300000000010
10000021003000000000 | 01002020203100003003
13000021003000000000 | 00100202020310000300
00001002020203100003 | 10300002100300000000
01030000210030000000 | 00001002020203100003
00003010020202031000 | 00100030000210030000
00010003000021003000 | 00003010020202031000
02020203100003003010 | 00210030000000001000
00021003000000000100 | 02020203100003003010

Cycle 3 - 44 rounds, 273 tricks
00020000000100000310 | 02031000003100302020
00203100000310030202 | 00020000000100000310
00000010020302030310 | 00100300010020000200
00010030001002000020 | 00000010020302030310
00203020303100000310 | 00100200002000000010
00020000000100000210 | 03031000003100302020
00303100000310030202 | 00020000000100000210
00000010030202030310 | 00100300010020000200 
00010030001002000020 | 00000010030202030310 
00302020303100000310 | 00100200002000000010
00010020000200000001 | 00302020303100000310
00000010030302020310 | 00100300010020000200
00010030001002000020 | 00000010030302020310
00303020203100000310 | 00100200002000000010
00010020000200000001 | 00303020203100000310
$\endgroup$
1
  • $\begingroup$ Thank you! I would love to read any publications about your results and Michele Cocco Lasta's ones. $\endgroup$ Mar 8, 2023 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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