Problem Description
Given two card rank values, the question is:
What is the probability that there
are one or more occurrences of the two values being adjacent or with only
one intervening card in a well shuffled standard 52 card deck?
Background & Techniques
Viewer Kevin asked the above question, maybe to win a
few beers from his buddies - he refers to the "guesser" as the "victim".
If I were a better mathematician, I could probably come up
with an analytical answer to the question. I'm not. and I
couldn't. Even knowing the experimental answer, I haven't succeeded in
setting up the permutations that define the possible outcomes.
The program finds the answer experimentally. For the
specified number of trials (100,000 by default), a "deck" is
"shuffled" and then checked for one or more matches meeting the specified
conditions. The deck consists of only card rank values 1 through 13
repeated 4 times to make and array of 52 integers. .
The matching procedure is to move through the deck from cards 1 trough
50, checking each card against the two cards following for a match
against the two test values, checked in either order. The card in
position 51 is, of course, only checked against card 52 for a match in
either order.
An additional option allows checking against the immediately following
card and not the 2nd following card.
If the number of matches in a deck is greater than zero, that trial
counts as a success.
Addendum - October 21,2006: Here is a follow-up question: Is
it possible to arrange a deck so that all 78 unique rank pairs meet the
condition? (In choosing pairs, we have 13 choices for the first card and
12 choices for the second or 156 altogether. But since [a,b] and b,a] are
identical for our purposes, we'll divide by 2 to get 78 choices.).
An second program "PerfectDeck", posted today, answers the
question. (Yes!)
The "Check Random decks" option generates random decks and counts the pairs
that meet the condition. It was not very successful; no perfect decks found
in 500,0000 decks checked.
The second search type, "hill climbing", starts with a random deck and swaps
pairs, keeping those that improve the score. It finds solutions rapidly, so
the trial stops after 1000 are found. There were some interesting
issues in this approach. If the pairs are chosen for swapping
systematically there are some deck configurations that will never lead
to a solution if we require each successful swap to produce a higher
score. If we allow swaps which match or exceed the current score,
solutions will be found. It would be interesting to find out
what these problem configurations look like.
Running/Exploring the Program
Suggestions for Further Explorations
Define the analytical solution!
In "Perfect Deck" program, study the problem configurations described
above.
|
Original Date: September 23, 2006 |
Modified:
October 22, 2006 |
|
