Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Shuffling a lot of cards


  • Please log in to reply
11 replies to this topic

#1 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 January 2012 - 12:38 AM

The card game Hand and Foot requires one more deck than the number of players. Assume four people are playing, thus there are five decks of 54 cards each (2 jokers and 4 each of A,2,3,4,5,6,7,8,9,10,J,Q,K).

The result of a round of play is a discard pile that is EXTREMELY non-random, with many contiguous strings of identically denominated cards. So, after a round of play, all players shuffle the cards.

In fact, shuffling takes place in rounds. In one round, everybody shuffles a bunch of cards (in the example above, about 65 cards per player) several times, and then finally passes half the cards to the person at the right.

Let's not worry about how many times they have to shuffle in order to "randomize" their bunch of cards. My question is:

How many ROUNDS of shuffling does it take to randomize the cards, if we assume that they are able to randomize the cards in their bunch?

Subsidiary question: what fraction of cards should be passed? That is, is it optimal to pass half the cards, or is there a better fraction.

I don't have an answer to this question. I do know that we get tired of shuffling...
  • 0

#2 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 07 January 2012 - 02:14 AM

I'll venture an initial guess for a good number of rounds to be twice the number of players, and I base this guess on absolutely nothing. ;) Though players+1 seems like a good guess too.

Just curious, when would you call the decks randomized? It seems you could get to the state where every situation could occur, but they wouldn't all have the same probability of occurring (and it may be impossible to reach uniformly random regardless of the number of rounds).

That said, I'm thinking something like either 1/e or 1-(1/e) will be the optimal proportion of cards to pass (or maybe something like 1-(1/(e^p)) where p is the number of players).

Could the optimal proportion of cards change for each round? Like it is best to pass 1/2 the first time, then 1/3 etc.

Actually, it's hard to see a better proportion than 1/2 for 2 players as it maximizes the entropy. I'll think about this further...

Great Post :)
  • 0

#3 phillip1882

phillip1882

    Senior Member

  • Members
  • PipPipPipPip
  • 765 posts

Posted 07 January 2012 - 03:50 AM

it seems to me that the best way would be to randomize with the passing phase. each player gets an initial set of cards, then deals them out to all other players including himself in a random fashion, such that he gives each player roughly the same number of cards. have all players do this simultaneously for maximum randomness. one round of this should be all that's required.
  • 0

#4 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 January 2012 - 05:27 AM

EventHorizon, certainly more than a little flaw in the OP--what do I mean by randomized?

In this game, color and suit don't matter, only denomination. So randomization should result in a uniform distribution of each denomination in the deck. I realize this is still rather vague, sorry, but it's a clue.

Phillip1882, since my question focused on the concern about mixing the cards from one person with those of the next, I like your suggestion very much--your proposal separates contiguous cards across all the players immediately, in one (or each) passing round.

As an aside, for those who aren't familiar with Hand and Foot, the need to separate the cards is manifest in several of the pre-play activities. For one thing, after all players shuffled and passed, etc., ALL players deal, and they each deal two hands (of 13 cards). Then they pass them to their left and right neighbors (in two-hand, they pass one hand and keep the other).. Then the remaining undealt cards are put into two draw piles, and each person's turn starts by drawing one card from each draw pile.

I'm liking your discussions, folks, keep those cards and letters coming...
  • 0

#5 thoughtfulfellow

thoughtfulfellow

    Advanced Member

  • Members
  • PipPipPip
  • 218 posts

Posted 07 January 2012 - 07:56 AM

EventHorizon, certainly more than a little flaw in the OP--what do I mean by randomized?

In this game, color and suit don't matter, only denomination. So randomization should result in a uniform distribution of each denomination in the deck. I realize this is still rather vague, sorry, but it's a clue.

Phillip1882, since my question focused on the concern about mixing the cards from one person with those of the next, I like your suggestion very much--your proposal separates contiguous cards across all the players immediately, in one (or each) passing round.

As an aside, for those who aren't familiar with Hand and Foot, the need to separate the cards is manifest in several of the pre-play activities. For one thing, after all players shuffled and passed, etc., ALL players deal, and they each deal two hands (of 13 cards). Then they pass them to their left and right neighbors (in two-hand, they pass one hand and keep the other).. Then the remaining undealt cards are put into two draw piles, and each person's turn starts by drawing one card from each draw pile.

I'm liking your discussions, folks, keep those cards and letters coming...

Spoiler for My approach

  • 0

#6 phillip1882

phillip1882

    Senior Member

  • Members
  • PipPipPipPip
  • 765 posts

Posted 07 January 2012 - 08:10 AM

okay went ahead a wrote a program to explore this problem further.
got that with giving player half, it takes roughly 3.37 rounds for a good distribution.
surprisingly, keeping 1/2.718 seems to increase the number of rounds necessary to a solid 4.
with my method, i got a good distribution roughly 63% of the time.

Edited by phillip1882, 07 January 2012 - 08:12 AM.

  • 0

#7 thoughtfulfellow

thoughtfulfellow

    Advanced Member

  • Members
  • PipPipPip
  • 218 posts

Posted 07 January 2012 - 09:44 AM

From phillip1882's analysis, 3.37 rounds is 13 passes. I set up a spreadsheet to run different scenarios. Five decks of 54 cards each would be 67.5 cards each (for ease of formulas, I accepted the concept of a half card here). I ran the distribution of passing different numbers of cards and found that the best distribution after 13 passes was by passing 34 cards (here I did not use fractional cards) which was only slight improvement over 33 cards passed each time. I ran several variations and did get slight improvement by doing variations on number passed per round but have not found any with sufficient improvement to reduce the number of passes to 12 and achieve the same threshold of distribution.
  • 0

#8 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 January 2012 - 06:09 PM

with my method, i got a good distribution roughly 63% of the time.


Let me make sure I understand your method. Here's my paraphrase:

divide the deck into n slabs, one per player.
each player deals his/her slab into 4 piles (by "deals", I assume you mean deals a card to each pile in turn, until all the cards are gone) [I realize you suggested dealing somewhat randomly, but I doubt that is necessary--dealing individual cards to different piles sounds powerful in separating the same-denomination runs]
each player distributes the piles to the 4 players (including self)

Then each player shuffles the cards in the 4 piles they now have.
And that's it.

Or do we do this more than once?

If doing this merely once does a good job, you're going to have a lot of friends at our house!
  • 0

#9 CaptainEd

CaptainEd

    Senior Member

  • Members
  • PipPipPipPip
  • 1094 posts

Posted 07 January 2012 - 06:13 PM

From phillip1882's analysis, 3.37 rounds is 13 passes.

I fear that my sloppy use of language has done some damage.

By a "round" of shuffling, I meant that all players shuffle a while, then they all pass a fraction of their deck to the next player, simultaneously. So, I would think of 3.37 rounds as being 3.37 times when they all pass.
  • 0

#10 phillip1882

phillip1882

    Senior Member

  • Members
  • PipPipPipPip
  • 765 posts

Posted 07 January 2012 - 09:15 PM

your correct on both points captain ed. your description is spot on (minus the random deal), and as i said, this seems to give a good distribution (each player having roughly the the same number of each card value +/- 10%) 63% of the time. (i only tested it with the case of 4 people, but i doubt that percentage will vary by much.)
so you may want to do 2 rounds of this to be sure. with the standard shuffle and pass, i got an average of 3.37 rounds. and if you think about it that makes sense. after shuffling, each player will have roughly half his cards and half the cards the opponent gave him mixed together, so after giving up half, he'll roughly have 1/4 his cards and 1/4 the cards from his opponent. (plus the new half of course.)

so my estimate for a general formula will be that you need to mix and pass roughly (number of players) -1

Edited by phillip1882, 07 January 2012 - 09:20 PM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users