Discrete Mathematics for Computer Science

Exercises 505

W Exercises

1. Suppose S is a set with k elements. How many elements are in S', the cross product

Sx S x ... x S of n copies of S?

2. Suppose that F'=l ai = ' bj = I where 0 < ai, bj < 1. Use the Product of

Sums Principle to prove that '__l F_'-= ai -bj = 1. Does the result hold if some

of the ai and bj can be less than zero and greater than one?

3. Suppose -n I ai = 2, E-'jI bj = 3, and E/=I ck = 5. Evaluate

n m l

-ai ( l bj Ck)

___ =1k=1

4. Consider the Birthday Problem, ignoring leap years. Determine the probability that
   two people in your class have the same birthday under each of the following circum-
   stances:
   (a) There are 20 people in your class.
   (b) There are 30 people in your class.
   You may wish to use a calculator.


5. Suppose that people are equally likely to be born on each of the seven days of the
   week. In a group of n people, determine the probability that:
   (a) Two or more of them were born on Saturday.
   (b) Exactly two of them were born on Saturday.
   (c) Two or more of them were born on the same day of the week.


6. For the network described in Example 2 in Section 8.3.2, determine the probability of
   each of the following events:
   (a) Each node can communicate with the other two.
   (b) At least two links are down.
   (c) A is directly connected to B.


7. A coin is tossed, a die is rolled, and a card is drawn at random from a deck. Assume
   that the toss, roll, and draw are fair.
   (a) Describe this experiment as a cross product sample space.
   (b) With the aid of a tree diagram, define a probability density on the cross product.
   (c) Verify by direct computation that the probability density found in part (b) is legit-
   imate.
   (d) Does it matter in what order the coin, the die, and the card are considered?


8. Two dice are rolled. One is fair, but the other is loaded: It shows the face with six spots
   half the time and the remaining five faces with equal frequencies.
   (a) Describe the experiment in terms of a cross product sample space.
   (b) Define a probability density on the cross product space.
   (c) Verify by direct computation that the probability density found in part (b) is legit-
   imate.
   (d) Does it matter in what order the dice are considered? Explain your answer.