Page 487 - Discrete Mathematics and Its Applications

466 7 / Discrete Probability

The probability that there are either k mutual friends or k mutual enemies in the group of n
n
( )
k
people equals p( i=1 E i ). Using Boole’s inequality (Exercise 15), it follows that
⎛ n ⎞ n
( ) ( )
k k k(k−1)/2
n 1
p ⎝ E i ⎠ ≤ p(E i ) = · 2 .
k 2
i=1 i=1
n
k k−1
By Exercise 17 in Section 6.4, we have ≤ n /2 . Hence,
k
k(k−1)/2 k k(k−1)/2
n 1 n 1
2 ≤ 2 .
k 2 2 k−1 2
Now if n< 2 k/2 ,wehave

1
1
n k k(k−1)/2 2 k(k/2) k(k−1)/2 2−(k/2)
2 < 2 = 2 ≤ 1,
2 k−1 2 2 k−1 2
where the last step follows because k ≥ 4.
n
( )
We can now conclude that p( k E i )< 1 when k ≥ 4. Hence, the probability of the
i=1
complementary event, that there is no set of either k mutual friends or mutual enemies at the
party, is greater than 0. It follows that if n< 2 k/2 , there is at least one set such that no subset
of k people are mutual friends or mutual enemies.

Exercises

1. What probability should be assigned to the outcome of 7. What is the probability of these events when we randomly
heads when a biased coin is tossed, if heads is three times select a permutation of {1, 2, 3, 4}?
as likely to come up as tails? What probability should be a) 1 precedes 4.
assigned to the outcome of tails? b) 4 precedes 1.
2. Find the probability of each outcome when a loaded die c) 4 precedes 1 and 4 precedes 2.
is rolled, if a 3 is twice as likely to appear as each of the d) 4 precedes 1, 4 precedes 2, and 4 precedes 3.
other five numbers on the die. e) 4 precedes 3 and 2 precedes 1.
3. Find the probability of each outcome when a biased die is 8. What is the probability of these events when we randomly
rolled, if rollinga2or rollinga4is three times as likely select a permutation of {1, 2,...,n} where n ≥ 4?
as rolling each of the other four numbers on the die and a) 1 precedes 2.
it is equally likely to rolla2ora4. b) 2 precedes 1.
c) 1 immediately precedes 2.
4. Show that conditions (i) and (ii) are met under Laplace’s
d) n precedes 1 and n −1 precedes 2.
definition of probability, when outcomes are equally
e) n precedes 1 and n precedes 2.
likely.
9. What is the probability of these events when we randomly
5. A pair of dice is loaded. The probability that a 4 appears
on the first die is 2/7, and the probability that a 3 appears select a permutation of the 26 lowercase letters of the En-
on the second die is 2/7. Other outcomes for each die glish alphabet?
appear with probability 1/7. What is the probability of 7 a) The permutation consists of the letters in reverse al-
appearing as the sum of the numbers when the two dice phabetic order.
are rolled? b) z is the first letter of the permutation.
c) z precedes a in the permutation.
6. What is the probability of these events when we randomly
d) a immediately precedes z in the permutation.
select a permutation of {1, 2, 3}?
e) a immediately precedes m, which immediately pre-
a) 1 precedes 3. cedes z in the permutation.
b) 3 precedes 1. f) m, n, and o are in their original places in the permu-
c) 3 precedes 1 and 3 precedes 2. tation.