On a recent episode of The Math Factor podcast, they discussed a very simple game. Start with a deck of some number of cards and a round table of some number of people (preferably more than one of each). The dealer deals one card to each player (going around clockwise starting with the player on the dealer's left) until all cards are dispersed. The last person to get a card is the new dealer. The new dealer picks up the cards she has been dealt and deals those out in the same manner. Play continues until someone has all of the cards.
Because each position can only come from one
and can only lead to one
child position, you are guaranteed that
you will always get back to the starting state if you play long enough.
Someone else may win before that, but you are guaranteed that you will
never get into a loop where no one will win. Or, I should say, that
is so long as no one misdeals.
It turns out that for two players with 52 cards, the game should take 12 turns if everyone deals correctly. But, I wanted to explore all of the possible loops you could get into with a misdeal. There are 15 different loops altogether. Each is summarized by one row of this image:
A dot in the zero-th column means that the first dealer has 0 cards and the other player has 52 - 0 cards. Similarly, a dot in the n-th column (starting the counting with zero) means that at some point in the cycle, the first dealer would have n cards and the other player would have 52 - n cards. The dot is blue if the first dealer has the deal and red if the second player has the deal.
With a different number of cards, situations arise where the first-dealer has n cards and the deal but later has n cards but not the deal. Those would be depicted as yellow in my scheme. But, that doesn't occur with 52 cards. Try two players and 2 cards to see how it could come up.
The length of a cycle is the sum of the red and blue dots plus twice the number of yellow dots in the row.
Because these are closed loops and the
is totally determined by the parent position, you can start at any
point to reveal the whole cycle. For instance, from the top row,
we can see there is blue in 49 and red in 45, 38, and 24. So, say
we started with player 1 having 24 cards, player 2 having the other
28, and player 2 having the deal (this is the red in the 24 spot).
The deal would give 14 more cards to player 1 for a total of 38
and leave player 2 with 14 cards and the deal. The next deal would give
7 more cards to player 1 for a total of 45 and leave player 2 with
7 cards and the deal. The next deal would give 4 more cards to
player 1 for a total of 49, leave player 2 with 3 cards, and give
the deal to player 1. The next deal leaves player 1 with 24 cards
and gives the deal back to player 2. This is where we started.
It is interesting to note that except in the degenerate last line where the dealer starts with no cards, the second player always has the deal at the point when the first player has the fewest cards he'll ever have during the cycle. The picture somewhat masks the fact that the non-degenerate lines are mirrors of others where the mirror flips things left to right and swaps red for blue. The missing mirror of the degenerate line is because I only checked loops that had the first player dealing at least once. So, I suppose there should be a 16-th row with just a red dot in the last column.
I basically used the following code, dumped it into
vim nuked the
) stuff, did a
sort -u on it, changed the zeros to
1 1 1 changed the ones to
0 0 1 and changed the twos to
1 0 0, then slapped a
P3 53 53 1 header on it, pulled it into GIMP and plopped the grid on it.
(defun picture-row (start) (let* ((total (reduce #'+ start)) (flags (make-array (1+ total) :element-type 'fixnum))) (labels ((rec (start start-dealer cur dealer cntr) (if cur (incf (elt flags (elt cur 0)) (expt 2 dealer))) (if (and (equalp start cur) (eql start-dealer dealer)) cntr (multiple-value-bind (cur dealer) (next-position (or cur start) dealer) (rec start start-dealer cur dealer (1+ cntr)))))) (rec start 0 nil 0 0)) (format t "~A~%" flags))) (defun picture (cards) (dotimes (ii (1+ cards)) (picture-row (v 'integer (- cards ii) ii))))