From Puzzles to Programming

PUZZLES OF PROBABILITY

 

1. What is the number of ways of selecting 5 cards without replacement (i.e. each card withdrawn is not returned back) from a deck of 52 cards?

Answer

First card can be selected in 52 ways. When it is drawn, the next card can be selected in 51 ways, the third card can be in 50 ways....so, the 5 cards can be selected in 52x51x50x49x48 different ways.

2. What is the number of words of length 5 that can be chosen from the set of letters {a, b, c, d, e, f, g} without repeating letters?

Answer

The first letter can be any of the above 7 letters; the second letter can be selected from only 6 remaining letters, and so on ... Therefore, it is equal to 7x6x5x4x3 = 2520 words.

Here, we should define permutation term. If we have a set S of n elements, then an r-permutation of the set S is any ordered listing of r elements of S where r is an integer <= n. The first element can be assigned to n elements, the 2^nd assigned to (n-1) elements, 3^rd to (n-2) elements,¡¦and r element assigned to (n-r+1) elements. Therefore, r-permutation = P (n, r) = n(n-1)(n-2)¡¦.(n-r+1).

Note that definition of n! = n(n-1)(n-2)¡¦(n-r+1)(n-r)(n-r-1)¡¦¡¦1 = P(n, r) (n-r)!. Hence, P(n, r) = n! / (n-r)!

In the above example, P(7, 5) = 7! / 2! = 7x6x5x4x3. In example 25, P(52, 5) = 52! / 47! =  52x51x50x49x48

3. What are the combinations of the five objects {a, b, c, d, e}, taken three at a time regardless of the arrangement?

Answer

These combinations are: (abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde) i.e 10 objects. If we take arrangement into consideration then these combinations would be simply the 3-permutations P(5,3) = 5x4x3 = 60 objects that we found in the previous examples i.e.

     abc, acb, bac, bca, cab, cba

     abd, adb, bad, bda, dab, dba

     abe, aeb, bae, bea, eab, eba

     acd, adc, cad, cda, dac, dca

     ace, aec, cae, cea, eac, eca

     ade, aed, dae, dea, ead, eda

     bcd, bdc, cbd, cdb, dbc, dcb

     bce, bec, cbe, ceb, ebc, ecb

     bde, bed, dbe, deb, ebd, edb

     cde, ced, dce, dec, ecd, edc

We notice that each of these 3-combinations was repeated in the 3-permutations 3! = 3x2x1 = 6 times. Example abc was repeated 6 times in the first row and so on. Therefore, the total number of combinations 3 taken at a time regardless of the arrangement of letters would be P(5,3)/3! = 60/6 = 10.

In general terms, the number of combinations C of n objects taken k at a time is equal to

C(n, k) = P(n, K)/k! = n!/[(n - k)!k!] 

 

Simliar Case:

A group of points [A, B, C, D, E] are connected to each other with lines as below. How many triangles do they form?

 

 

Answer:

The triangles formed are ten: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, and CDE.

The problem can be simplified as finding the combinations of five points {A, B, C, D, E}, taken three at a time regardless of the arrangement. Therefore, applying the rule C(5,3) = 5!/3!(5-3)! = 10 triangles.

A generalization can be made: If n points are all connected to each other, then the number of geometrical figures having m sides formed is equal to C (n, m). In the above example, there are C (5,4) = 5 four sided figures: ABCD, ABCE, ABDE, ACDE, and BCDE.

 

4. A poker hand is a set of 5 cards chosen from a deck of 52 cards. The order in which the cards are chosen is irrelevant. How many poker hands are there?

Answer

Applying the above equation of example 27, there are

C(52, 5) poker hands = 52x51x50x49x48/5x4x3x2x1 = 2,598,960

 

5. What is the probability that each card of a poker hand is spade (spade poker hand)?

Answer

The probability that a poker hand is all spade is actually the number of all spade hands divided by the total number of all poker hands.

The number of all poker hands was determined by example 28 as C(52, 5).

The number of all spade hands is actually the number of all the combinations of the 13 spade cards chosen 5 at a time i.e. C(13, 5)

Hence, the solution is C(13,5)/C(52,5) = 13x12x11x10x9/52x51x50x49x48 = 0.0005 meaning 5 in 10,000 chance of getting a spade poker hand.

 

6. What is the probability that a poker hand has exactly 2 kings, 2 queens and 1 ace?

Answer

As in the previous example let's find the number of the poker hands with the above outcome. There are 4 kings, 4 queens, and 4 ace in a deck of 52 cards. The number of ways in which 2 kings are selected from 4 kings is C(4, 2). The number of ways in which 2 queens can be selected is C(4, 2). The number of ways in which 1 ace can be selected is C(4, 1). Each outcome of the C(4, 2) 2-kings can coexist with any of the outcomes of the C(4, 2) 2-queens. Hence, the total number of possible outcomes of the 2-kings and 2-queens together would be C(4, 2) x C(4, 2). The number of the poker hands with the three conditions satisfied would be C(4, 2) x C(4,2) x C(4,1). To get the probability of having this kind of poker hand, we divide by C(52, 5)

 

7. Birthday Problem: In a room of n persons, each of the 365 days of the year is equally likely to be someone's birthday. Intuitively, it may seem that at least 365 people should be present to have a chance of 50% that at least 2 of them will have the same birthday. However, using the probability theory, prove that only n = 23 persons need to be present to have a 50% chance that 2 persons have the same birthday.

Answer

The probability that a person will have any of the birthdays is 365/365. The chance that a second person will not have the same birthday is 364/365. The chance that a third person's birthday does not match those of the first 2 peoples is 363/365. Now, the chance of these successive independent events occurring is the product of the probability of the events occurring separately. Therefore, the probability that the nth person asked will not have the same birthday is:

(365/365)(364/365)(363/365)¡¦¡¦((365-(n-1))/365). Therefore, the probability that the nth person asked will provide a match is 1 minus (365)(364)¡¦((365-(n-1))/(365)©ú. From this formula, only n = 23 persons are needed to have a chance of 50.7% that 2 persons will have the same birthday. Only 55 people are needed so that the chance is 98.6%. In other words, if you have a group of 55 people, there is almost 100% chance that 2 will have the same birthday.

 

8. In a lot of 100 fuses is inspected as follows: 5 fuses are chosen at random and tested; If all 5 blow at the correct amperage, the lot is accepted. If there are 20 defective fuses in the lot, what is the probability of accepting the lot?

Answer

The number of all possible combinations of 5 fuses chosen from 100 is C(100, 5). The number of possible combinations of 5 good fuses is C(80, 5). Therefore, the probability of choosing 5 good fuses i.e. accepting the lot is

C(80, 5)/C(100, 5) = 0.32

In general, let X be the number of defective fuses among the 5 that are inspected. The space of X is set {x=1,2,3,4,5} and the probability density function of X f(x) or (the probability of X = x) or the probability that x defective fuses are chosen is calculated as follows:

The number of ways x defective fuses are chosen from 20 defective fuses is C(20, x). The number of ways the remaining (5-x) good fuses are chosen from the 80 good fuses will be C(80, 5-x). Therefore,

f(x) = C(20, x)C(80, 5-x)/(100, 5)  where x = 0,1,2,3,4,5 else f(x) = 0 elsewhere. This type of distribution is called hyper-geometric distribution.

 

 

 

 

 

9. A bowel contains 5 chips. Three of the chips are marked $ 1 and two are marked $ 4 each. A blindfolded player draws at random and without replacement, two chips from the bowel. The player is paid an amount equal to the sum of the values of the two chips that he draws. If it costs $ 4.75 to play this game, would it be cost effective to play this game? In other words, would the expectation of winning equal or greater than the amount the player paid?

Answer

First, we find the hyper-geometric distribution f(x) or the probability of X = x where X represent the number of chips, of the two to be chosen, that are marked $ 4.

Then f(x) = C(2, x)C(3, 2-x)/C(5, 2) where x=0,1,2

And f(x)=0 elsewhere.

Now, the value v(x) that a player will win depending on x is: 4x + (2-x) = 3x+2 dollars

The expectation E is the summation of the values v(x) multiplied by the probability of getting x for each x=0,1, and 2. i.e. E = ¢²(3x+2)f(x) = ¢²[(3x+2)C(2,x)C(3,2-x)/C(5,2)] as x goes from 0,1, to 2. E = 44/10 = $ 4.4

Therefore, the expectation for winning is less than what the player would pay to play the game.