Suprising shuffle
Chas F Brown
Take a deck of normal playing cards, with 4 suits and 13 ranks. Shuffle
it, and lay the cards out, face up, into 13 columns of 4 cards each
(equivalently, 4 rows of 13 cards each).
Let an operation consist of reordering the cards within any column,
without exchanging cards between columns. You are permitted as many
operations as you desire.
It turns out that it is always possible to perform these column
operations so that *each* of the 4 *rows* of 13 cards contains *exactly*
one card of each rank.
In fact, this is true if we have a deck of r ranks, and s suits; lay out
the cards into r columns of s cards each; it is always possible to
rearrange the cards within the columns (without exchanging cards between
columns) so that there are s rows, each row containing exactly 1 card of
each rank. In fact, it remains true when we have a countable number of
ranks and a finite number of suits.
Is there a name for this (sort of like the pigeonhole principle)?
Cheers - Chas
--
---------------------------------------------------
C Brown Systems Designs
Multimedia Environments for Museums and Theme Parks
---------------------------------------------------
Gerry Myerson
Chas F Brown <cbr...@cbrownsystems.com> wrote:
=> Take a deck of normal playing cards, with 4 suits and 13 ranks.
=> Shuffle it, and lay the cards out, face up, into 13 columns of 4
=> cards each (equivalently, 4 rows of 13 cards each).
=>
=> Let an operation consist of reordering the cards within any column,
=> without exchanging cards between columns. You are permitted as many
=> operations as you desire.
=>
=> It turns out that it is always possible to perform these column
=> operations so that *each* of the 4 *rows* of 13 cards contains
=> *exactly* one card of each rank.
This is the "Solitaire" part of the paper, Marriage, Magic, and
Solitaire that David B. Leep and I published in the American
Mathematical Monthly in May, 1999 (volume 106, pp 419 to 429).
The "Marriage" part of the title refers to Hall's Marriage
Theorem, which is what David and I used to prove the result.
--
Gerry Myerson (ge...@mpce.mq.edi.ai) (i -> u for email)
Fred Galvin
> Take a deck of normal playing cards, with 4 suits and 13 ranks. Shuffle
> it, and lay the cards out, face up, into 13 columns of 4 cards each
> (equivalently, 4 rows of 13 cards each).
>
> Let an operation consist of reordering the cards within any column,
> without exchanging cards between columns. You are permitted as many
> operations as you desire.
>
> It turns out that it is always possible to perform these column
> operations so that *each* of the 4 *rows* of 13 cards contains *exactly*
> one card of each rank.
>
> In fact, this is true if we have a deck of r ranks, and s suits; lay out
> the cards into r columns of s cards each; it is always possible to
> rearrange the cards within the columns (without exchanging cards between
> columns) so that there are s rows, each row containing exactly 1 card of
> each rank. In fact, it remains true when we have a countable number of
> ranks and a finite number of suits.
The number of ranks can even be uncountable.
> Is there a name for this (sort of like the pigeonhole principle)?
It goes by various names. I'd call it the common transveral theorem.
Given an arbitrary set E (the deck of cards in your example), a
positive integer n (n = 4 in your case), and two partitions of E into
n-element sets (the partition of the deck into aces, kings, queens,
etc., and the partition into columns of your array), there exists a
common transversal for the two partitions, i.e., a subset of E which
has exactly one element in common with each part of each partition
(you can take this as the first row of your reshuffled array);
repeating this, you can get a partition of E into n sets, each of
which is a common transversal of the two given partitions.
Philip Hall used this theorem to show that, if H is a finite subgroup
of a (finite or infinite) group G, then there is a common transversal
for the system of left cosets and the system of right cosets. This is
still true for an infinite subgroup of finite index, but it breaks
down for infinite subgroups of infinite index.
See L. Mirsky, _Transversal Theory_, Academic Press, 1971, ISBN
0-12-498550-5.
--
It takes steel balls to play pinball.
Chas F Brown
This wouldn't, by any chance, be the game of solitaire where you shuffle
the cards, then lay them out, one at a time, saying "ace, two, three,
...., jack, queen, king, ace, two, ..., etc."; if you turn over a card
and say its rank, then you lose?
That's where this problem comes from - I thought my brother made up the
game! Probability of winning (going through the whole deck without ever
saying a rank that matches the turned over card) is approximately 1/e^4
(and approximately 1/e^s for r ranks, s suits); and I needed the above
result to prove it.
I'll have to look up the article.
Cheers - Chas