The Math Factor Podcast

10 Comments »

1. nklein said,

   May 5, 2008 at 4:29 pm

   I just wanted to add another reason this makes a very bad bar bet: any misdeal gets you out of the good circuit. Chaim said two players with 52 cards takes 7 deals. But, if two cards stick together unnoticed on deal five, you’ve got to hope for some very special misdeals in the future to get you back on track.

   There are 53 ways to divide the cards between two people. Only 7 of those ways are on the good loop. You don’t want to end up in the other 46.

   (It is only 7 and not 14, right? because it matters who is dealing…)

2. trivial34 said,

   May 5, 2008 at 9:07 pm

   I have been working on this problem daily since I heard the first show on the wonderful game of Tag Deal. I have a few interesting observations to report along with my progress. I noticed on the show and in the comments that people are trying to find a pattern for a given number of players with a varying number of cards. I do not believe this is the right way to look at this. If we look at a given number of cards and vary the number of players, the cycle length is much more orderly. In fact, for k cards and p>=k-1 players the cycle lengths form an arithmetic sequence with a common difference that is always a power of 2. This common difference will be 2^Ceiling(log_2 k) where k is the number of cards. This has given me hope that a formula for at least all cycle lengths of k cards and p>=k-1 players exists. Since we can calculate these differences we almost have a formula. All we need to find is a formula which gives us the cycle length for k cards and k-1 players (which I call the stabilized values) and then add the correct number of differences. The sequence of stabilized values is even more surprising. Making a table of differences between these values (and then a table of the differences between those!) shows a really nice pattern forming. I don’t have the proper notation or typeset to display the differences here but I’m sure if you make a table you’ll see the pattern. The patterns are recursive which is giving me trouble but I think I am getting very close to a formula. Let me know what anyone can make of these patterns.

3. nklein said,

   May 7, 2008 at 6:45 pm

   Ugh. I cannot figure out how to put an image inline here in the comments.
   So, I’m just going to point you to my LiveJournal.

4. djogon said,

   May 9, 2008 at 10:38 am

   I created a little program that calculates the tags, saves the states of each player and the graphically represents them. It may help, but it is highly amusing to see how the number of required tag varies with different number of players/cards.

   I planned to create more graphical representations that may help “discover” a patter or at least look pretty :)

   Anyway…
   You can pick it up from
   http://www.softwareriver.com/download/orderlychaos.zip

   You only need to have .NET 2.x on your computer and it should run. Select the number of cards, players and select start.
   You will then see a graphical representation of each tag as a line for each player.
   The player with no cards will have an empty line – the player with all cards will have the full line for that tag (row).
   Starting player is colored blue.

   If the “graph” cannot fit in your window a red line will show up indicating that there is more so try to resize your window.

   Have fun!

5. tydie1 said,

   May 19, 2008 at 3:35 pm

   I made a program to find out total deals for different scenarios. I thought that it would be fun to see exactly how long it would take to do the extreme case mentioned in the podcast, 20 players and 500 cards. After 2 weeks of running this most of the time on my computer I have found that it will take more than 845,108,046 rounds and I would heed the advice not to try this at home.
   For anyone who might want to continue this calculation the last round I calculated was as stated above round 845,108,046 and the players had these amounts of cards 1:83 2:15 3:13 4:60 5:67 6:44 7:11 8:41 9:5 10:30 11:23 12:9 13:41 14:6 15:17(DEALER) 16:10 17:13 18:4 19:5 20:3

6. mkudzin said,

   May 21, 2008 at 4:56 pm

   Tydie1,

   I suspect (but cannot prove, of course) that this configuration cannot be brute forced in any reasonable amount of time. I ran through approximately 500 billion iterations this morning and did not reach the end. Based on experiments with 500 cards and fewer players (7 or 8 players are manageable), I would not be suprised if (20,500) requires many orders of magnitude more iterations.

7. tydie1 said,

   May 29, 2008 at 12:45 pm

   I kind of figured that out after I started that it would take a very long time. I guess it is a good thing I stopped it because if it is orders of magnitude more than 500 billion it could have taken over my computer for the rest of my life and probably still not gotten to the end.

8. mkudzin said,

   June 1, 2008 at 12:26 pm

   Perhaps this will help. It is the key part of my program, written in C,
   to count the number of deals for a given number of players and cards.
   The code is not particularly intuitive, but it is VERY fast. Here is a
   brief description of how it works:

   1.) The key observation is that as the cards are dealt out in round after
   rounds, each player will be given the same number of cards. (Although
   some will have received ONE more than others if the number of cards dealt
   is not divisible by the number of players.) Therefore, it is NOT NECESSARY
   to add the number of cards given to each players hand on each deal. All
   you have to do is keep track of how many cards each player is “owed” if you
   HAD added them.

   2.) The key variables are: “stacks”, “offset”, “dealer”, and “hand”.

   “stacks” is an array of integers that STARTS as the number of cards in each
   players hand. The first step in every round is for the new dealer to pick
   up all the cards in his hand. Therefore, the dealer’s stack is decreased
   by the number of cards he has. IF we wanted to KEEP “stacks” as the number
   of cards in each player’s hand, we would then have to add to EACH stack
   the number of cards that EACH player is dealt. We don’t bother doing that.
   Instead, we increase a single variable, “offset”, by the number of cards
   that each player should receive. Thus, in general, the number of cards
   in player i’s hand is “stacks[i] + offset”. (Actually, this may be off by
   one, depending on whether player i has gotten the one extra card as a result
   of a partial deal.)

   “dealer” is the index of the current dealer. “hand” is the number of cards
   in the dealer’s hand.

   3.) In general, each player will receive hand/players cards, rounded down.
   The dealer’s position will advance by the remainder hand%players. Since this
   division is time-consuming, I use two lookup tables, “qtable” and “rtable”,
   to store the precomputed quotients and remainders.

   4.) According to my description in (2), it seems like the number stacks[0]
   should be initialized to cards, since at the beginning, the first player
   has all the cards, and offset should be initialized to zero. If that were
   the case, then the code to compute the number of cards in the dealer’s hand
   would be:

   
hand = offset + stacks[dealer];
if (dealer != 0)
      hand++;


   This is because, most of the time, the dealer will be one of the players
   who has received one additional card from the fact that the number of cards
   dealt is not divisible by the number of players. The one exception is when
   the current dealer is the same as the original dealer, in which case, the
   total number of cards dealt IS divisible by the number of players, and all
   the players, including the current dealer, has received exactly the same
   number of cards.

   In order to simplify and speed up the computation of the number of
   cards in the dealer’s hand, I initialize offset to one, so that the
   increment is automatically performed. However, that would give the
   initial dealer one too many cards, so I initialize his stack to
   cards-1.

   5.) “count” keeps track of the number of deals. I have not given you a
   definition for the counter datatype. What you choose to use will depend
   on your application. For small examples, count can just be an integer.
   However, on my computer, I go through approximately 135,000,000 deals
   per second. At that rate, you will overflow a 32-bit integer in less
   than a minute. Of course, your milage may vary.

   6.) I have also included a routine to print out the number of cards in
   each player’s hand. It is not used in the main program, but I hope it
   will be helpful in understanding the code. If anyone wants, I will be
   happy to send them the complete, working code.

   ———-

   
int qtable[MAX_CARDS], rtable[MAX_CARDS];

   counter *play_game(int players, int cards)
   {
         int loop, offset, dealer, hand, *stacks;
         counter *count;

         // Initialize lookup tables used to avoid performing
         // divisions on each iteration.
         for (loop=0; loop<=cards; loop++) {
              qtable[loop] = loop/players;
              rtable[loop] = loop%players;
         }

         // Initialize stacks.
         stacks = malloc(players*sizeof(int));
         stacks[0] = cards - 1;
         for(loop=1; loop<players; loop++)
              stacks[loop] = 0;
         offset = 1;
         dealer = 0;
         hand = cards;
         initialize_counter(count);

         // main loop
         do {
              increment_counter(count);
              stacks[dealer] -= hand;
              offset += qtable[hand];
              dealer += rtable[hand];
              if (dealer >= players) {
                   dealer -= players;
                   offset++;
              }
              hand = offset + stacks[dealer];
         } while (hand < cards);

         free(stacks);
         return count;
   }

   void print_stacks(int players, int *stacks, int offset, int dealer)
   {
         int i, hand;

         printf("( ");
      for(i=0; i<players; i++) {
           hand = offset + stacks[i];
           if (i > dealer)
                hand--;
           printf("%d ", hand);
      }
      printf(")\n");
}


9. trivial34 said,

   July 13, 2008 at 2:24 pm

   For the past three months I have working on the problem of finding a formula for the number of deals it takes for the cards to cycle. As of early this morning I have found a formula for any game with p>=c-1 where p is the number of players and c is the number of cards. The formula is far from simple and has to do with the sum of the digits of binary numbers. For now, the validity of my formula rests solely on my intuition and passing any abitrary test, however I will begin to prove every step of my derivation soon. Any game with p<c-1 seems to be far too random to formulate but I will not say it is impossible.

10. tydie1 said,

    June 13, 2009 at 1:02 pm

    http://www.research.att.com/~njas/sequences/A003558
    If you take this sequence and replace the initial 2 with the number of players and n with the number of cards it seems to fit. I don’t think this really helps with calculating large values though.

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.

Podcast powered by podPress v8.8.10.17