May 8th, 2008


More Card Dealing Loops

This is a follow-on to a previous post.

Alice and Bob are playing a game described in The Math Factor podcast. Alice starts with some number of cards. She deals them out to Bob and herself one at a time until she is out of cards. If she got the last card, she is the next dealer. If Bob got the last card, Bob is the next dealer. The next dealer picks up the cards she or he has and deals them in the same manner. Play continues until one person has all of the cards.

In my previous post, I showed a diagram for all of the loops possible with 52 cards. This post shows all of the loops for anywhere from 2 to 100 cards. In my previous post, I showed rows that were basically mirrors of each other (swap Bob and Alice). In these pictures, I have eliminated this redundancy and the degenerate case where the dealer starts with no cards.

As a refresher, each row represents one loop. For nn cards the image is (nn + 1) squares wide. A blue square in column kk (counting columns starting at zero) means that at some point in that loop, Alice had kk cards and the deal. A red square in column kk means that at some point in that loop, Alice had kk cards but Bob had the deal. A yellow square in column kk means that twice during the loop, Alice had kk cards: once when she had the deal and once when Bob had the deal.

Collapse )

A state is totally defined by the number of cards Alice has along with who has the deal. With nn cards, there are 2 * nn possible states (not counting the two degenerate cases where the dealer has no cards). Some lines start with a red dot then have all yellow up to a final blue dot. Those lines hit every one of the 2 * nn states. I expected such cases to be isolated, but they occur at 5 & 6 cards 29 & 30 cards and at 89 & 90 cards.

I have much improved my code, and placed it on github. Most of the improvement comes from uniqing and sorting the lines and using xach's handy Vecto library to draw the images full-size directly to png with the grid lines and everything. I have a feeling Vecto will figure big in many future visualization tasks.

Collapse )