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
