Comments on: DU. Chaos at the Card Table

By: trivial34

trivial34 — Fri, 25 Apr 2008 12:54:23 +0000

It is also notable that for k cards the cycle length will stabalize for all players greater than or equal to (k-1) in the sense that the cycle lengths begin to form an arithemetic sequence with a common difference being a power of two (so I’ve found thus far) I haven’t been able to prove this yet but I’ve tested it for 2->15 cards (1 is a trivial case).

Common differences for k cards after k-1 players for 2->15 cards

1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16

The non technical reason I presume is that once there are k-1 players, the cards have enouh room to go around without overlapping. Then, adding more players just increases the number of times one card has to travel around the table. Since the common differences all seem to be powers of two this might say something about how many times the cards travel all the way around the table (adding one more player increases the number of turns by one each time we go around the table, so increasing my some power of two indicates a number of times around)

The main conclusion is that the cycle length is chaotic only for k cards and p

By: strauss

strauss — Fri, 25 Apr 2008 00:02:14 +0000

It’s quite interesting to consider how long it takes for the cards return to a single pile. With four players, for example, and 1 through 40 cards, the number of tag-deals required to complete the hand are

1, 4, 7, 12, 11, 11, 48, 41, 68, 24, 33, 164, 136, 186, 285, 31, 283,
273, 332, 395, 176, 676, 888, 65, 713, 273, 399, 578, 2175, 360, 59,
327, 2037, 219, 1857, 255, 191, 1712, 1739, 5344

(So with four players and seven cards, 48 tagdeals are required!! But look how chaotic the numbers seem!)

Incidentally, do NOT try this with a deck of 52 cards. For 2,3,4,5, 6 and 7 players, the number of tagdeals required are 12, 867, 5872, 91105, 519243 and 1670867 respectively…)

What is going on here?

Another thing to consider is:

If we consider a “state” to be the number of cards in each place, reading around from the current dealer, each state uniquely tagdeals to another, and uniquely is tagdealt from another. So every state lies on a cycle and there are some number of cycles among the possible states.

If we have n players and k cards, (and so (n+k-2)!/(n-1)!/(k-1)! possible states) how many cycles will there be? How long will they be?

By: jlundell

jlundell — Mon, 21 Apr 2008 06:00:25 +0000

I was stuck on this one until a friend pointed out that the deal function has an inverse. Then everything falls into place.

By: stevestyle

stevestyle — Mon, 21 Apr 2008 05:58:39 +0000

The procedure is reversible. Given any position we can calculate the previous position, as well as the next position. As there are a finite number of positions we must get into a loop. That would bring us back to the starting position where the original dealer has all the cards.

By: mkudzin

mkudzin — Sun, 20 Apr 2008 17:59:02 +0000

It is possible to write down a simple formula to “solve” the problem in the special case of two players and n cards.

The original dealer will have all of the cards after k deals where 2^k = 1 (mod 2n+1).

The other player will have all of the cards after l deals where 2^l = -1 (mod 2n+1).

There is always such a number, k. There does not have to be such an l. However, if it exists, the smallest l will be half of the smallest k.

I put the words “solve” in quotation marks because finding k or l requires computing a discrete logarithm. There is no good algorithm for computing discrete logarithms. So, in practice, finding k or l requires roughly the same amount of work as just playing the game.

Since I don’t want to spoil the fun, I leave the proof of this “solution” as an exercise to the reader.