In October of 1779, Euler prepared for the St. Petersburg Academy a paper on “a curious question from the doctrine of combinations.” So great was the backlog of Euler's writings that this was not published in the Academy's Memoirs until 1811, more than a qurter-century after his death. This delay notwithstanding, he provided an example not only of a “curious” problem but also a method of attack—[redacted]—that has become one of the primary weapons in the combinatorial arsenal.
The problem had been posed, and solved, decades earlier. In 1708, Pierre Remond de Montmort (1678-1719) discussed a card game called Treizeor, more descriptively, Rencontre (“coincidence”). The rules are these: a player shuffles a deck of 13 cards from ace to king, then deals them one at a time saying “one” with the first card dealt, “two” with the second, and so on. Victory is achieved if at some point the card overturned exactly matches the word spoken—for instance, if the fourth card turned over is a “four” or the eleventh card laid down is a “jack.” should such a coincidence occur, the dealer wins.
Montmort determined the probability of winning thereby earning for himself a place of honor in the history of combinatorics....
—William Dunham, Euler: The Master of Us All
9 comments:
I have, by tedious enumeration, determined the odds for a dealer playing with a deck of 2, 3 or 4 cards.
This produced an unexpected and surprisingly simple pattern that allows me to guess the odds of playing with 13 cards.
The "surprisingly simple pattern" was detected in error.
For a 2-card deck, the odds of success are 1/2.
For a 3-card deck, six card orders are possible. In two of these, the ace is first, resulting in a win. Of the two cases where the ace is second, one (2-1-3) gives a win. And when the ace is last, one case wins (3-2-1).
So with 3 cards, four out of six win, and the odds are 2/3.
With four cards, there are 4! possible card orders, or 24.
Six of them have the ace first, giving six wins.
When the ace is second, there are wins for 2-1-3-4, 3-1-2-4, and 4-1-3-2, three wins.
When the ace is third, there are wins for 2-3-1-4, 3-2-1-4, 4-2-1-3, three wins.
When the ace is last, there are wins for 2-4-3-1, 3-2-4-1, 4-2-3-1, three wins.
Overall there are fifteen wins, giving odds of 15/24, a little less than the 3-card case.
I came up with an answer and wrote a simulation to verify it. The simulation says the odds of winning is around 0.6321. It coincided with my answer.
However, when I came here to describe my approach it didn't make sense at all. I don't know what I thought writing that, and can't explain it now. But it seems to work! Here it is:
\sum^13_{k=1} (-1)^(k+1) C(13,k) (N-k)! / N!
I tried to use inclusion-exclusion principle. I think, although my initial idea was wrong, it somehow formulates the right thing. Maybe I am just tired.
That notation means a summation from k=1 to k=13, right? What is N?
Can you use your method to calculate probabilities for the small sizes like 2, 3 and 4? (When I say a deck of 3, I mean ace, 2 and 3, not three random cards.)
Okay, now I figured it out. The formula is indeed correct. N is the number of cards, in our case 13.
I am going to demonstrate the approach using 3 cards (A, B, C) and we will generalize. All possible orderings of three cards are (winning conditions are marked with †):
A B C †
A C B †
B A C †
B C A
C A B
C B A †
We need to count the number of orderings where at least one card is in place. Let's count the instances where A, B and C is in place separately. I am going to put a * symbol next to the row where this happens.
A B C ***
A C B *
B A C *
B C A
C A B
C B A *
In total we have 6. But we have counted the first row three times. We need to subtract those extra counts. First let's count instances where (A,B), (A,C) and (B,C) is in place.
A B C ***
A C B
B A C
B C A
C A B
C B A
So there are 3 instances where 2 of the cards is in place. 6-3 = 3 is our sum. But we have counted instances where 3 cards are in place so we have subtracted more than we wanted. We have to add those. The only instance where 3 cards in place is the first row so the answer is 6-3+1 = 4.
Because we have used only 3 cards everything happened regarding to the first row, don't let this misguide you, if we used 4 cards we should have seen other rows counted.
Now let's generalize. If we have N cards, f(N,k) being the number of instances where k cards are in place, the formula we have is (a.k.a. inclusion-exclusion principle):
f(N,1) - f(N,2) + .... + (-1)^N f(N,N-1) + (-1)^(N+1) f(N,N)
f(N,k) is the number of instances where k cards are in place. The number of instances where single k element configuration, say (A,B) for k=2, being in place in N cards is (N-k)!. For example there are (N-2)! instances where (A,B) is in place. Think of fixing k elements and remaining elements are permuted. There are C(N,k) such k element configurations. In total there are N! orderings. So the probability of seeing k elements in place is:
C(N,k) * (N-k)! / N!
If we put everything together the formula becomes:
∑₁ᴺ (-1)^(k+1) C(13,k) (N-k)! / N!
This is a great analysis, thanks! I'll continue with the book and see if it describes Euler's approach in a similar way.
A friend here discovered a more elegant way.
If we somehow count the number of instances where no card is in place the answer is: 1 - [# of losing configurations]/N!
Say, the number of losing configurations of length N is c(N). Imagine replacing 1st card with 6th card
1 -> 6
...
6 -> X
....
Now there are two possibilities. Either 6 is matched with 1, or 6 is matched with other number. If it is matched with 1, there are c(N-2) configurations from there. Because you can remove 1 and 6 and the size of the remaining set is N-2. If 6 is matched with some number other than 1 there are c(N-1) configurations from there (it is a little bit tricky to show but doable).
Then the number of configurations where no card is in place is: c(N) = (N-1) (c(N-1) + c(N-2))
Now you can compute 1-c(N)/N!
I have been trying to verify your first formula. The general form should not have a 13, as below, correct?
∑₁ᴺ (-1)^(k+1) C(N,k) (N-k)! / N!
You did't give a value for your final answer, but the result from your simulator has an interesting "possible closed form".
Of course, I forgot to substitute 13=N in that formula.
Wow that approximate closed form might not be coincidence at all.
Post a Comment