<h1>Regarding Beggar-My-Neighbour</h1>
<p>Paulhus (1, p.164) wrote in 1999:</p>
<blockquote>
<p>If <span class="math-container">$C$</span> is a full deck of cards, does <span class="math-container">${D_{2}}^{'}(C)$</span> 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.</p>
</blockquote>
<p>But Conway et al. (2, p.892) wrote in 2006:</p>
<blockquote>
<p>Strip-Jack-Naked, or Beggar-My-Neighbour **1</p>
<p>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).</p>
<p>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.</p>
<p>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?”  <strong>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.</strong></p>
<p>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.</p>
<p>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.</p>
</blockquote>
<p>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.</p>
<p>In 2013, Lakshtanov and Aleksenko (3) wrote:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>but their rules are not the ones I followed when I played the game when I was a child ;-)</p>
<p>To the best of my knowledge the longest Beggar-my-Neighbour game was found in 2014 by <a href="https://plus.google.com/107844874222105920188/posts/fvQepUuXnsZ" rel="nofollow noreferrer">William Rucklidge</a> with <a href="http://www.richardpmann.com/beggar-my-neighbour-records.html" rel="nofollow noreferrer">7960 cards</a>:</p>
<pre><code>1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK
</code></pre>
<h1>Regarding Cavacamicia</h1> 
<p>I usually played it with a 40 cards deck, simulations with an half deck (only 20 cards) gives <a href="https://github.com/alessandro-gentilini/pelagaletto2/blob/master/README.md" rel="nofollow noreferrer">16 non terminating games</a> on a total of <a href="http://www.wolframalpha.com/input/?i=20%21%2F%282%21*2%21*2%21*14%21%29" rel="nofollow noreferrer">3.448.400</a> games.</p>
<h1>Bibliography</h1>
<p>(1)
PAULHUS, Marc M. Beggar my neighbour. <em>American Mathematical Monthly</em>, 1999, 162-165.
<a href="http://www.jstor.org/stable/2589054" rel="nofollow noreferrer">http://www.jstor.org/stable/2589054</a></p>
<p>(2)
BERLEKAMP, Elwyn R.; CONWAY, John H.; GUY, Richard K. <em>Winning Ways for Your Mathematical Plays, Volume 4.</em> AMC, 2003, 10: 12.
<a href="http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays-volume-4" rel="nofollow noreferrer">http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays-volume-4</a></p>
<p>(3)
LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finiteness in the Beggar-My-Neighbor card game. <em>Problems of Information Transmission</em>, 2013, 49.2: 163-166.
<a href="http://dx.doi.org/10.1134/S0032946013020051" rel="nofollow noreferrer">http://dx.doi.org/10.1134/S0032946013020051</a></p>

CC BY-SA 4.0
2023-03-14T20:52:07.850Z
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.
Kevin Wang
CC BY-SA 4.0
2024-05-20T15:42:34.660Z
A non-terminating game of Beggar-My-Neighbour has now been found: https://arxiv.org/abs/2403.13855 .  But finding one by brute force has proven inviable: no non-terminating sequence was found across many billion random games.
ms609
CC BY-SA 4.0
2024-06-23T14:01:04.673Z
@ms609 thank you very much for your valuable news!
Alessandro Jacopson
CC BY-SA 4.0
2015-10-20T19:04:01.117Z
2023-03-08T21:23:24.170Z
2023-03-08T21:23:24.170Z
Alessandro Jacopson
<h1>Digression</h1>
<p>Maybe since the time of asking you found the answer yourself...
However yes, &quot;Cavacamicia&quot; has cycles so sometimes it is non terminating.</p>
<p>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 &quot;not taking away the pleasure of search to other people&quot;.
He just published a one line note on a facebook page he had named &quot;Cavacamisa Straccia camicia Pelagalletto Infinita&quot;.</p>
<p>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.</p>
<p>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.</p>
<h1>Answer</h1>
<p>The following are some of the existing starting sequences that generates non terminating games.
All of these are related to three distinct cycles.</p>
<p>Only <code>Cycle 3</code> has balanced configurations in it (with 20/20 cards) while <code>Cycle 1</code> and <code>Cycle 2</code> can be reached from the given starting configurations but do not contain balanced configurations directly.</p>
<p>The search was not exaustive so I cannot say if there are other cycles on Cavacamicia.</p>
<pre><code>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
</code></pre>

CC BY-SA 4.0
2023-03-08T07:25:02.787Z
Thank you! I would love to read any publications about your results and Michele Cocco Lasta's ones.
Alessandro Jacopson
CC BY-SA 4.0
2023-03-06T21:57:00.520Z
2023-03-06T21:57:00.520Z
Diego Mazzaro
<p>Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"):</p>

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

<p>The players alternate placing down in a stack the next card from their deck.</p>

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

<ul>
<li>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.</li>
</ul>

<p>The first player to run out of cards loses the game.</p>

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

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

CC BY-SA 3.0
2014-04-17T22:58:28.993Z
A similar game is [Beggar-My-Neighbour](http://en.wikipedia.org/wiki/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](http://www.jstor.org/discover/10.2307/2589054?uid=3738296&uid=2&uid=4&sid=21103675600841) whether a non-terminating game exists or not.
Marzio De Biasi
CC BY-SA 3.0
2014-04-18T02:54:59.957Z
(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
CC BY-SA 3.0
2014-04-18T14:24:25.517Z
@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
CC BY-SA 3.0
2014-04-18T14:38:52.390Z
@EmanueleViola: you're right, if the same deck configuration appears two times the game will never end! I deleted the comment.
Marzio De Biasi
CC BY-SA 3.0
2014-04-18T18:04:37.630Z
This is Egyptian Rat Screw, but without the slapping!
argentpepper
CC BY-SA 3.0
2015-11-19T12:59:15.823Z
Is there any relationship between the *Collatz conjecture* and the problem  of Beggar-My-Neighbour?
Alessandro Jacopson
<board-games>
Does this game terminate?
Manu
# Does this game terminate?

(Asked by: username_0 on 2014-04-17)

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?

**Tags:** board-games

> **Comments:**
> **username_1**: A similar game is [Beggar-My-Neighbour](http://en.wikipedia.org/wiki/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](http://www.jstor.org/discover/10.2307/2589054?uid=3738296&uid=2&uid=4&sid=21103675600841) whether a non-terminating game exists or not.  
> **username_2**: (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!  
> **username_0**: @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.  
> **username_1**: @EmanueleViola: you're right, if the same deck configuration appears two times the game will never end! I deleted the comment.  
> **username_3**: This is Egyptian Rat Screw, but without the slapping!  
> **username_4**: Is there any relationship between the *Collatz conjecture* and the problem  of Beggar-My-Neighbour?  

---

## 2 answers

### Answer by username_4 on 2015-10-20. Score: 11

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

> **Comments:**
> **username_5**: 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.  
> **username_6**: A non-terminating game of Beggar-My-Neighbour has now been found: https://arxiv.org/abs/2403.13855 .  But finding one by brute force has proven inviable: no non-terminating sequence was found across many billion random games.  
> **username_4**: @username_6 thank you very much for your valuable news!  

---

### Answer by username_7 on 2023-03-06. Score: 5

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

> **Comments:**
> **username_4**: Thank you! I would love to read any publications about your results and Michele Cocco Lasta's ones.  

---

