This is G o o g l e's cache of http://vax.wcsu.edu/~sandifer/rencontre.htm as retrieved on Mar 20, 2004 23:30:15 GMT.
G o o g l e's cache is the snapshot that we took of the page as we crawled the web.
The page may have changed since that time. Click here for the current page without highlighting.
This cached page may reference images which are no longer available. Click here for the cached text only.
To link to or bookmark this page, use the following url: http://www.google.com/search?q=cache:b6hX500sDM0J:vax.wcsu.edu/~sandifer/rencontre.htm+Calculus+of+Probabilities+in+the+game+of+%E2%80%9Cco-incidence%E2%80%9D&hl=en

Google is not affiliated with the authors of this page nor responsible for its content.
These search terms have been highlighted: calculus probabilities game co incidence 

CALCUL DE LA PROBABILITE

DANS LE JEU DE RENCONTRE

by Leonhard Euler

Enestrom index number 201

Mémoires de l'académie des sciences de Berlin [7] (1751), 1753, p. 255-270

Opera Omnia, Series I volume 7, p. 11-25

translated for The Euler Project by Geoff Burke.

Calculus of Probabilities

in the game of "co-incidence"

1. The "game of co-incidence" is a game of chance for two players, where each has an entire deck of cards, and take turns drawing one card after another, until they arrive at the same card; then one of them wins. Now, if there is never a match, the other person wins. This poses the problem, what is the probability that one or the other player is going to win?

2. To better fix our ideas, we can suppose that one player is called A, and the other B, both having a certain and same number of cards marked with the numbers 1, 2, 3, 4, 5 etc. and each laying one card on the other until they get to the same number, then player A wins. If they lay all of the cards without any matches, player B wins.

3. As it is indifferent how each card is marked, we can suppose that A lays his tickets in the order 1, 2, 3, 4, 5, etc. Applying this to cards, one conceives of numbering the cards according to the order in which they were played successively by A, in this way number 1 is the card A plays first, number 2 second, number 3 third and so on.

4. In this way player A, who is ‘for the coincidence’ will win, when B plays his pack of cards: at the first go number 1, the second no 2, the third number 3, or the fourth number 4 etc. Now if he arrives where the number of the card played by B, which never corresponds to the number of the card played by A at the same time, B will win the bank. By this method, it seems that that research into the game is rendered easier by the application of calculus to it.

5. The question is then to determine the probability that either A or B will win the bank. What will be the number of cards or the numbered ticket. Because firstly we see this determination varies according to the number of cards, and becomes all the more complicated as the number of cards gets large. It will be suitable to start the research with a small number of cards and go on to arrive at successively larger numbers.

6. Suppose firstly that one or the other of the players has a single card marked 1, it is clear that ‘a coincidence’ will not be missed, A will infallibly win. In this case, the probability of A winning will be expressed as 1, and that for B as 0, since he has no chance of winning.

7. If A and B now have two cards, numbered one and two, and A plays his cards in the order 1 and 2. In this supposition, there will be two cases, where B plays his cards in the order 1 and 2, or 2 and 1. The first, giving a coincidence on the first go, will give a win to A, the other, giving no coincidences, will give a win to B.

8. Since one or the other of the two cases is equally likely, both A and B will have a case for a win. The probability of one or the other will be expressed as a ˝, and either of them will have a right to claim a half of the bank.

9. Now suppose that the two players each have three cards, marked 1, 2 and 3, and that A first plays 1, second 2 and third 3. Now B can play his cards in 6 different ways

A

B
 

1

2

3

4

5

6

1

1

1

2

2

3

3

2

2

3

1

3

2

1

3

3

2

3

1

1

2


and it is equally probable that each of these 6 cases will actually arise.

10. In these 6 cases there will be two, the first and the second, where A is going to win and where the game finishes at the first go; in the other four cases, there isn’t one, except the fifth, where A will win on the second go, and which finishes the game. In the other three cases, it is the third, where A wins on the third go.

11. Once again, in these 6 possible cases, there are 4 which favour A, and the other 2, the fourth and the sixth, put B in possession of the gain. So, A has 4 ways to win and B two, the chances for A are 4/6 = 2/3, and for B = 2/6 = 1/3; so the advantage for A is twice as much as that for B.

12. Now give each of our players 4 cards, 1, 2, 3, 4; and given that A plays his cards in the order 1, 2, 3, 4; the order of B’s cards can vary in 24 different ways:

A

B
 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

1

1

1

1

1

1

1

2

2

2

2

2

2

3

3

3

3

3

3

4

4

4

4

4

4

2

2

2

3

3

4

4

3

3

4

4

1

1

4

4

1

1

2

2

1

1

2

2

3

3

3

3

4

4

2

2

3

4

1

1

3

4

3

1

2

2

4

1

4

2

3

3

1

1

2

4

4

3

2

4

3

2

1

4

3

1

3

4

2

1

4

2

4

1

3

2

1

3

2

1

and each of the 24 cases is equally likely.

13. It is evident that the first 6 cases will give a win at the first go to A, and the game is finished, I have crossed out the numbers in these 6 columns. In the 18 remaining cases there are 4, numbered 17, 18, 21 and 22 where A wins at the second go, and the columns will be subsequently terminated. Fourteen cases continue through to the third round, there are 3, numbers 10, 12 and 20, which terminate the game in A’s favour. Finally, of the eleven remaining cases, there are two which give wins in the fourth and last round.

14. Having now 6 cases where A wins on the first go, 4 cases where he wins on the second go, 3 where he wins on the third go, and two where he wins on the fourth go, there will be a total of 15 cases favourable to A, with the remaining 9 where B wins. Consequently, the probability of A winning will be 15/24 = 5/8, and for B = 9/24 = 3/8. So the chances for A will be better than for B by 5 to 3.

15. If we now set the number of cards = 5, we will have 120 different cases for the variations that would have arisen in the order of the cards played by B, during which A plays his cards in the order 1, 2, 3, 4, 5. Now, that would be going too far, if we tried to represent all the cases, to see how many are going to be favourable to A or B, the large number of cards will render this impracticable.

16. Moreover such a numbering would actually not serve well to determine in general the chances for A and B, however large the number of cards. To this effect, I must make general remarks that we could construct using the knowledge of [probabilities for] large numbers of cards, knowing already the probabilities for small numbers.

17. I remark firstly that in general the number of cards being = m, there are going to be as many different cases as the product of all the numbers 1, 2, 3, 4, up to m (consisting of integers), where the number of cases is 1.2.3.4…m. Now, I suppose that A always plays his cards according to the numerical order 1, 2, 3, 4, …m, the order they are marked, and the product 1.2.3.4..m will give the number of cases which can arise in the order B plays his cards.

18. It is clear from the first principles of combinations, where one knows that the order of 2 cards can vary in 2 ways, 3 cards in 6 ways, 4 cards in 24 ways, 5 cards in 120 ways, 6 cards in 720 ways, 7 cards in 5040 ways, 8 cards in 40320 ways and in general m cards in as many ways as the product 1.2.3.4…m (consisting of integers).

19. This number of cases 1.2.3…m I propose to shorten to M, I remark that in the second place that there are going to be M/m cases where the first card played by B is 1, that there are M/m cases where the first card played by B is a 2, and there are going to be as many cases where the first card played by B is a 3 or a 4 or a 5 etc. on to m.

20. Moreover, if we were to leave out that the game finishes immediately, where B will be matching A’s card, and we suppose that they will continue to lay their cards until the end, we would have one or more coincidences, it is also clear that there are going to be M/m cases where the second card of B’s will be 2, and as many cases where the third card will be a 3, and the fourth card a 4, or the fifth 5, or the sixth 6 etc.

21. So, supposing they continue to play their cards until the end, there will be M/m cases where A wins on the first go, the same M/m cases where he wins at the second go, and as many cases where he wins at the third go and the fourth and the fifth etc. up to the last go.

22. But in effect, although there would have been M/m cases where A would win at the first go, there will not be as many cases where he can win at the second go, since the M/m cases which would win at the second go, in the preceding supposition, must remove those which had already had one win at the first go, because having already won at the first go, the game does not continue onwards.

23. There will be the same number M/m of cases where B plays card number 3, because he must remove the cases where they have already met, either on the first or the second go. For A to win at the fourth go, he must take away the number of all the cases which have been played, which is M/m which have already had one ‘coincidence’, in the first, second or third go.

24. In general then, the number of cases which will be won by A at one go will be M/m, from the preceding hypothesis, one must exclude all of those cases where we have found a ‘coincidence’ in any of the preceding rounds, so that the number of cases would be less and less the further the "go" is from the start.

25. To judge by how many the number of cases must diminish the number of favourable cases M/m at each go, or to know the number of those which have already ‘coincided’ in preceding goes, this is how I do it. I conceive that the card which coincides in the proposed go will be removed at one or other play, and the order of the cards and the number of cases will be the same as if the number of cards were decreased by one.

26. To make all of this more intelligible, consider the case of 4 cards and the 24 cases found there, those where B plays as his third card number 3, which are the cases marked 1, 6, 10, 12, 20, 21 Take away the case with the card marked with a 3, and we have

A

B

1

1

1

2

2

4

4

2

2

4

4

1

1

2

4

4

2

1

4

2

1

Which are precisely the cases we would have for the three cards marked 1, 2 and 4.

27. Since these are the cases where B played number three as his third card, and where one had to take away those which already had a coincidence, either on the first go or the second, it is clear that the number taken away is found in the case of three cards, by adding together all of the cases where A wins on the first or the second go.

28. In general then, if the number of cards = m and if we want to know by how many we must decrease the number of cases M/m, which have had a coincidence at some preceding go, we must have recourse to the number of cards m-1, and then search the cases which will give a win to A at any of the preceding goes; and the number of all the cases together will be those which must decrease the number M/m, for to have the number of all the cases which will make A actually win at a proposed go.

29. Putting down the number of cards = m and the number of all the cases which we set = 1.2.3..m = M and

a the number of cases in which A wins at the first go

b the number of cases in which A wins at the second go

c the number of cases in which A wins at the third go

d the number of cases in which A wins at the fourth go

e the number of cases in which A wins at the fifth go

etc.,

and we have seen that a = M/m; for the other numbers b, c, d, e, etc. we will soon see their progression.

30. We now see that the number of cards is a very large magnitude, = m+1, and the number of all the cases will be = 1.2.3.4.5….(m+1) = M(m+1)

which we will call M’.

We will see what happens next by setting

a’ the number of cases in which A wins at the first go

b’ the number of cases in which A wins at the second go

c’ the number of cases in which A wins at the third go

d’ the number of cases in which A wins at the fourth go

e’ the number of cases in which A wins at the fifth go

etc.

  1. That said, we have


a’ = M’/(m+1) = M;

and continuing the game, notwithstanding coincidences which have already arisen, there will also be M cases where there was a coincidence at the second go, but from these, one must exclude the ones where we have already had a coincidence at the first go, this number being a, as we have seen in §29, we will have


b’ = M – a

for the number of cases where A actually wins at the second go.

  1. The number of cases where the coincidence occurs at the third go will also be M, and if we exclude those which have already had a coincidence at the first or second go, that is to say where A has already won at the first or second go, when the number of cards will be lessened we will find that the number of cases where A actually wins at the third go will be

c’ = M – a – b.

33. It is the same number of cases which will give a win to A at any of the preceding goes, and moving on, one knows the number a, b, c, d, e, etc., for the number of cards = m, we have easily drawn the number a', b', c', d', etc. since the number of cards = m+1, because we will have

a’ = M,

b’ = M – a,

c’ = M – a – b,

d’ = M – a – b – c,

e’ = M – a – b – c - d

etc.

34. Knowing this, when the number of cards is m=1 and M = 1, that is a = 1, we have for two cards

a’ = 1 and b’ = 1 – 1 = 0.

Putting m = 2 and having M = 2, a =1 and b = 0, we have for three cards

a’ = 2, b’ = 2 – 1 = 1, c’ = 2 –1 – 0 = 1.

Supposing now that m = 3 and having M = 6, a = 2, b = 1, c = 1, we have for four cards

a’ = 6, b’ = 6 – 2 = 4, c’ = 6 – 2 – 1 = 3, d' = 6 – 2 – 1 – 1 = 2.

35. In this fashion, we can continue these numbers, with the number of cards, as large as we would like, and can better see the progression represented in the following manner

Number of cards
 

I

II

III

IV

V

VI

VII

VIII

IX

X

a

1

1

2

6

24

120

720

5040

40320

362880

b

-

0

1

4

18

96

600

4320

35280

322560

c

-

-

1

3

14

78

504

3720

30960

287280

d

-

-

-

2

11

64

426

3216

27240

256320

e

-

-

-

-

9

53

362

2790

24024

229080

f

-

-

-

-

-

44

309

2428

21234

205056

g

-

-

-

-

-

-

265

2119

18806

183822

h

-

-

-

-

-

-

-

1854

16687

165016

i

-

-

-

-

-

-

-

-

14883

148329

k

-

-

-

-

-

-

-

-

-

133496

36. If we divide these numbers by the number of all possible cases which correspond to each number of cards, we will derive from them the odds of A to win at the first go.

Number of cards

1

2

3

4

5

6

7

8

9

etc.

Odds of A

1

1/2

1/3

1/4

1/5

1/6

1/7

1/8

1/9

etc.

From which we conclude, if the number of cards is n, the odds of A winning on the first go will be 1/n.

37. If we consider the numbers in the table (§35) we see firstly that each number is the difference of the one above and the one preceding. In this way, if the number of cards = m, the number of the case which wins for A at a certain go is p, the number of cases which will win at the same go, if the number of cards is m+1, will be q, and the number of cases which make a win at the next go = r, the number of cards remaining = m+1, we will always have

r = q - p.

38. Thus for m cards, the number of all the cases will be = 1.2.3.4..m = M, the odds of A winning at a certain go will be p/M, which I will call P. Now, for m+1 cards, the number of all the cases will be M(m+1), the odds of A to win at the same go will be q/M(m+1), which I will call Q, and the odds of a win in the following go = r/M(m+1), which I will call R. This said, we have

R= (q - p)/M(m+1)

or R = Q - P/(m+1).

39. Setting the number of cards = n-1, since the odds of A winning at the first go = 1/(n-1), for the number cards = n, the odds of A to win at the second go will be

= 1/n - 1/n(n - 1) = (n-2)/(n(n-1).

40. Now, if the odds of A to win at the second go, when the number of cards = n-1, being

(n-3)/(n-1)(n-2),

we conclude that, when the number of cards is n, the odds of winning at the third go will be

(n-2)/n(n-1)) - (n-3)/n(n-1)(n-2) = (n2 - 5n + 7)/n(n-1)(n-2) = ((n-2)2 - (n-3))/n(n-1)(n-2).

41. From this we conclude in the same manner that for the number of cards = n, the odds of A to win at the fourth go will be

= ((n-2)2 - (n-3))/n(n-1)(n-2) - ((n-3)2 - (n-4))/n(n-1)(n-2)(n-3).

= ((n-3)(n-2)2 - 2(n-3)2 + (n-4))/n(n-1)(n-2)(n-3) - ((n-4)(n-3)2 - 2(n-4) 2 + (n-5))/n(n-1)(n-2)(n-3)(n-4).

And the odds at the fifth go will be

((n-3)(n-2)2 - 2(n-3)2 + (n-4)) /n(n-1)(n-2)(n-3) - ((n-4)(n-3)2 - 2(n-4) 2+(n-5))/n(n-1)(n-2)(n-3)(n-4).

= ((n-4)(n-3)(n-2)2 - 3(n-3)2 (n-4)) + 3(n-4) 2-(n-5))/n(n-1)(n-2)(n-3)(n-4).

 

 

42. After a little reflection on the formulation of these formulae, one finds that the number of cards being n, the odds of A to win will be

at the first go

= 1/n

at the second go

= 1/n – 1/n(n-1)

at the third go

= 1/n – 2/n(n-1) + 1/n(n-1)(n-2)

at the fourth go

= 1/n – 3/n(n-1) + 3/n(n-1)(n-2) – 1/n(n-1)(n-2)(n-3).

at the fifth go

= 1/n – 4/n(n-1) + 6/n(n-1)(n-2) – 4/n(n-1)(n-2)(n-3) + 1/n(n-1)(n-2)(n-3)(n-4).

at the sixth go

= 1/n – 5/n(n-1) + 10/n(n-1)(n-2) – 10/n(n-1)(n-2)(n-3) + 5/n(n-1)(n-2)(n-3)(n-4) – 1/n(n-1)(n-2)(n-3)(n-4)(n-5)

etc.

 

 

43. Now the odds for A to win in general, at some go that we know, will be expressed by the sum of all the formulae taken together. Now, the number of these formulae will be equal to the number of cards n, the sum of all the first terms will be

n.1/n = 1

Next the sum of the numerators of the second term will be

1 + 2 + 3 + … + (n-1) = n(n-1)/2

the sum of all the second terms will be

= 1/1.2

And because

1 + 3 + 6 + 10 + … + (n-1)(n-2)/1.2 = n(n-1)(n-2)/1.2.3

the sum of the third terms is

1/1.2.3

and the sum of the fourth

1/1.2.3.4

the fifth

1/1.2.3.4.5

and so on.

44. From this, it follows that

The number of cards being

The odds that A will win

1

1

2

1 – 1 / 1.2

3

1 – 1 / 1.2 + 1 / 1.2.3

4

1 – 1 / 1.2 + 1 / 1.2.3 + 1 / 1.2.3.4

5

1 – 1 / 1.2 + 1 / 1.2.3 + 1 / 1.2.3.4 – 1 / 1.2.3.4.5

6

1 – 1 / 1.2 + 1 / 1.2.3 + 1 / 1.2.3.4 – 1 / 1.2.3.4.5 + 1 / 1.2.3.4.5.6

seeing from this table that there are always as many terms as there are cards.

45. The odds for A are then largest in the case of one card and smallest in the case of two cards. Next, one sees that when the number of cards is odd, the odds for A are always larger than for all of the even numbered cases. But if the number of cards is even, then the odds for A are less than for all the odd numbers of cards.

46. Having found the odds for A, one has only to take it away from unity to have the odds for B; because the odds of one and the other denote the share of the bank, that one or the other can pretend to by virtue of the probability which each has to win outright. Thus the odds for A being x, the odds for B will be 1 – x.

47. The formulae I have just found for the odds for A will easily reduce to decimal fractions, from where one can better judge their values. Thus, having made the calculations, I find:

Number of cards

Odds for A

Odds for B

1

1.000000000

0.000000000

2

0.500000000

0.500000000

3

0.666666666

0.333333333

4

0.625000000

0.375000000

5

0.633333333

0.366666666

6

0.631944444

0.368055555

7

0.632142857

0.367857143

8

0.632118055

0.367881945

9

0.632120811

0.367879189

10

0.632120536

0.367879464

11

0.632120561

0.367879439

12

0.632120558

0.367879442

13

0.632120559

0.367879441

14

0.632120558

0.367879442

15

0.632120558

0.367879442

etc.

    

48. So if we neglect the decimal fractions we find after the ninth position, we can say, where the number of cards is greater than 12, the odds of A and for B will not vary much, however large the number of cards becomes. In this way, when the number of cards is not less than 12, we can say that odds for A will be 0.632120558 and those for B 0.367879442.

49. Provided that the number of cards is not less than 12, the odds of A against B will always be approximately 12 to 7, or a little more accurately 122 to 71, or even more accurately 1720 to 1001. So, given 19 games to play, there will probably be 12 where A wins and 7 where B wins.

50. If the number of cards becomes infinite, the odds of A winning can be expressed by the infinite series

1 – ˝ + 1/6 – 1/24 + 1/120 - 1/720 + etc.

and the odds for B by this one

1 – 1 + ˝ - 1/6 + 1/24 – 1/120 + 1/720 – etc.

If we let e be the number whose (natural) logarithm = 1, we know that 1/e is the sum of the last series. So for the case n=Ą the odds for A will be 1 – 1/e and those for B will be 1/e, where

e = 2.718281828459045235360.

51. Substituting this value for e, one finds the odds for A, against those for B are

1.718281828459045235360 to 1,

and this proportion will be exact if the number of cards is larger than 20. Consequently it will be very accurate for the case where the game is played with an entire deck of 52 cards.

[Translator's note]

Le jeu de rencontre, or the game of coincidence, is described in "Euler – Master of us all" by W Dunham, as a game where a deck of 13 cards is shuffled by a player, who then counts the number of the card when he turns it over, i.e. he says ‘one’ when turning over the first card, 'two' the second etc. If the number of the card corresponds with the number spoken, the dealer wins. If this never happens by the time he gets to the end, he loses. This is probably a precursor to the game analysed in this paper.