Skip to content

10.17 Counting and Probability

  • Problem 1

If there are 30 people in a room (assume that no one is born on February 29 and that any day has the same chance of being anyone's birthday)

  1. What is the probability of at least two of them to have the same birthday? .
  2. What is the probability that exactly two people in the room have the same birthday?

Solution
First, we compute the probability that no two people have the same birthday, corresponding to event B. As discussed above, B is an ordering of length 30 (\(k=30\)) from a set of cardinality 365 (\(n=365\)), so \(P(B)=\frac{|B|}{|\Omega|} = \frac{365 \times \cdots \times (365 - 30 + 1)}{365^{30}} \approx 0.29\)
The event that at least two people have the same birthday is the complement of event B, so the probability that at least two out of the 30 people have the same birthday will be close to 71%.

Now we consider a slightly different question: what is the probability that exactly two people in the room have the same birthday? To construct such an example, we would need to

The total number of ways of selecting an outcome in the event 'exactly two people have the same birthday' is \(\binom{30}{2} 365 \times 364 \times \cdots \times (365 - 28).\)
Finally, to compute the probability of exactly two people having the same birthday, we need to divide by the cardinality of all possible birthday combinations given by \(365^{30}\), which gives approximately 0.38 or 38%. - Problem 2

Compute the probability that 10 married couples are seated at random at a round table, then no wife sits next to her husband.

Solution

If we let \(E_i, i=1,2,\dots,10\) denote the event that the \(i\)-th couple sits next to each other, it follows that the desired probability is \(1-P\left(\bigcup_{i=1}^{10} E_i\right)\).

Now, from Theorem 2, \(P\left(\bigcup_{i=1}^{10} E_i\right)=\sum_{i=1}^{10} P\left(E_i\right)-\sum_{i_1<i_2} P\left(E_{i_1} E_{i_2}\right)+\cdots+(-1)^{n+1} \sum_{i_1<i_2<\cdots<i_n} P\left(E_{i_1} E_{i_2} \cdots E_{i_n}\right)+\cdots-P\left(E_1 E_2 \cdots E_{10}\right)\)
To compute \(P\left(E_{i_1} E_{i_2} \cdots E_{i_n}\right)\), we first note that there are \(19!\) ways of arranging 20 people around a round table. (Why?) The number of arrangements that result in a specified set of \(n\) men sitting next to their wives can most easily be obtained by first thinking of each of the \(n\) married couples as being single entities. If this were the case, then we would need to arrange \(20-n\) entities around a round table, and there are clearly \((20-n-1)!\) such arrangements. Finally, since each of the \(n\) married couples can be arranged next to each other in one of two possible ways, it follows that there are \(2^n(20-n-1)!\) arrangements that result in a specified set of n men each sitting next to their wives. Therefore, \(P(E_{i_1} E_{i_2} \cdots E_{i_n}) = \frac{2^n(20-n-1)!}{19!}\)
To compute the full union probability, we must consider all possible combinations of couples at each step of the Inclusion-Exclusion formula. The term \(\binom{10}{n}\) accounts for the number of ways to choose n couples out of the 10. For example:

  • The term \(\binom{10}{1}\) represents the number of ways to choose exactly one couple to sit together. We choose one couple out of ten, which is \(\binom{10}{1} = 10\) ways. Each of these single-couple events has a probability of \(\frac{2^1(20-1-1)!}{19!} = \frac{2 \cdot 18!}{19!}\).
  • The term \(\binom{10}{2}\) represents the number of ways to choose exactly two couples to sit together. We choose two couples out of ten, which is \(\binom{10}{2} = 45\) ways.
  • This pattern continues for all n couples.

Thus, the probability that at least one married couple sits together is
​\(\binom{10}{1} \frac{2^1(18)!}{19!} - \binom{10}{2} \frac{2^2(17)!}{19!} + \binom{10}{3} \frac{2^3(16)!}{19!} - \cdots - \binom{10}{10} \frac{2^{10}9!}{19!} \approx .6605\)
Finally, the desired probability that no wife sits next to her husband is the complement \(1 - P\left(\bigcup_{i=1}^{10} E_i\right) \approx 1 - .6605 = .3395\) - Problem 3

The Coin on the Infinite Chessboard : A coin of radius \(r\) is tossed onto an infinite chessboard, where each square has a side length of 1. What is the probability that the coin lands entirely within the boundaries of a single square?

Solution
First, we define the Sample Space (\(\Omega\))
This problem can be solved by considering a single, representative \(1 \times 1\) square. The position of the coin is determined by the coordinates of its center, \((X,Y)\). Assuming the center is uniformly distributed over the square: \(\Omega = \{(X,Y) | 0 \leq X \leq 1, \quad 0 \leq Y \leq 1\}\)
The measure (area) of the sample space is: \(|\Omega| = 1 \times 1 = 1\)
Now, we define the Favorable Event \((A)\)
The event A that the coin lands entirely within the square occurs if and only if the center of the coin, \((X,Y)\), is at a distance of at least r from all four boundaries of the \(1 \times 1\) square.

image

This condition restricts the center's coordinates to the following range:

  • The center must be at least r units away from the left edge \((X=0)\) and the right edge \((X=1)\):
    ​\(r \leq X \leq 1-r\)
  • The center must be at least r units away from the bottom edge \((Y=0)\) and the top edge \((Y=1)\):
    ​\(r \leq Y \leq 1-r\)

The region of the favorable event A is a central square with a reduced side length \((1-2r)\). The area of the favorable event \(|A|\) is: \(|A| = ((1-r)-r) \times ((1-r)-r) = (1-2r)^2\)

The probability \(P(A)\) is the ratio of the favorable area to the total sample space area: \(P(A) = \frac{|A|}{|\Omega|} = \frac{(1-2r)^2}{1} = (1-2r)^2\)

Assumes a specific radius, \(r=\frac{1}{3}\). Substituting this value into the general formula: \(|A| = \left(1-2\cdot\frac{1}{3}\right)^2 = \left(\frac{3-2}{3}\right)^2 = \left(\frac{1}{3}\right)^2 = \frac{1}{9}\)

Thus, the final probability is: \(P(A) = \frac{1}{9}\)

‍