Interleaving Sorted Sequences and Decks of Cards
Arjun Ray
[Cross-posted as I'm not sure where best to post the problem. Please
set followups appropriately. Thanks.]
The total number of possible deals in contract bridge is 52!/13!^4.
IINM (which may be the problem!), this is the same as the number of ways
in which a standard deck of 52 cards can be arranged such that the cards
of each suit are still in rank order. (That is, the number of ways to
start with the cards of each suit in sorted order and then to merge them
into a single sequence by selecting an in-order card one at a time from
any of the four suits.)
This equivalence bothers my intuition. Concatenating the four hands of
a bridge deal generally does not produce a properly interleaved deck,
and giving each player 13 cards at a time from an interleaved deck does
not reproduce all possible deals.
What am I missing about the correspondence?
Mark Brader
> The total number of possible deals in contract bridge is 52!/13!^4.
>
> IINM (which may be the problem!), this is the same as the number of ways
> in which a standard deck of 52 cards can be arranged such that the cards
> of each suit are still in rank order. (That is, the number of ways to
> start with the cards of each suit in sorted order and then to merge them
> into a single sequence by selecting an in-order card one at a time from
> any of the four suits.)
Right. Basically, the same number arises because both actions involve
treating the deck of 52 cards as four sets of 13 cards.
> This equivalence bothers my intuition. Concatenating the four hands of
> a bridge deal generally does not produce a properly interleaved deck,
> and giving each player 13 cards at a time from an interleaved deck does
> not reproduce all possible deals.
You can construct a correspondence as follows. Start with a bridge
deal. Write down which hand the ace of spades is in, then which hand
the king of spades is in, then which hand the queen of spades is in,
and so on down to the two of clubs(*). You now have a list that looks
like south-east-east-north-west-south-...-north, with each direction
occurring 13 times. Change each instance of south, west, north, and
east to "spades", "hearts", "diamonds", and "clubs"(*) respectively.
Now simply construct your interleaved-sorted deck with the suits in
that order. The process is reversible if you want to go the other way.
(*) Any other specific order would do as well.
--
Mark Brader "All this government stuff, in other words,
Toronto is not reading matter, but prefabricated
m...@vex.net parts of quarrels." -- Rudolf Flesch
My text in this article is in the public domain.
Keith A. Lewis
>[Cross-posted as I'm not sure where best to post the problem. Please
>set followups appropriately. Thanks.]
Me either. I'm reading on sci.math, FWIW.
>The total number of possible deals in contract bridge is 52!/13!^4.
>
>IINM (which may be the problem!), this is the same as the number of ways
>in which a standard deck of 52 cards can be arranged such that the cards
>of each suit are still in rank order. (That is, the number of ways to
>start with the cards of each suit in sorted order and then to merge them
>into a single sequence by selecting an in-order card one at a time from
>any of the four suits.)
>
>This equivalence bothers my intuition. Concatenating the four hands of
>a bridge deal generally does not produce a properly interleaved deck,
>and giving each player 13 cards at a time from an interleaved deck does
>not reproduce all possible deals.
The minor coicidence that leads to your major coincidence is that the number
of suits is equal to the number of players (4). Therefore the number of
cards in a suit is equal to the number of cards in a hand, and de-permuting
each divides the number of possible (or meaningful) results by 13!, which
must be done 4 times in each case.
I think I have a mapping from the interleaved deck to the set of possible
bridge deals, but it requires 2 decks of cards. Deck A is sorted as you
describe above, deck B is sorted in factory order.
* Assign a suit to each player.
* Turn over the cards in deck A one at a time.
* The player whose suit is represented by the card from deck A gets the top
card from deck B dealt to him.
Each player will end up with 13 cards, potentially any set of 13 from deck
B. Of course, if players are allowed to watch the dealing they'll know all
the hands, so this wouldn't be a good way to play bridge in real life.
--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.