CS 70 Discrete Mathematics for CS

Fall 2004  Rao  HW 5

Due on Thursday, October 21 at 3:29PM

1. (15 pts.) Eulerian Paths and Cycles We proved in class that a connected (undirected) graph has an Eulerian cycle if and only if every vertex has even degree.

(a) Prove that if a graph G has exactly 2d vertices of odd degree, then there are d paths that together cover all the edges of G (i.e., each edge of G occurs in at least one of the d paths). Each of the paths should not contain any particular edge more than once.

(b) Suppose we have an (undirected) graph in which all vertices have even degree. Briefly describe how you would give a direction to each edge such that the indegree equals the outdegree of every vertex in the resulting directed graph.

(c) Find an undirected and connected graph with an Eulerian cycle that has an odd number of edges and an even number of vertices. Don’t use parallel edges or loops in your example.

2. (15 pts.) Poker hands In my favorite kind of poker, you are dealt five cards, selected from a deck containing 52 cards plus four different jokers. A flush is a hand where all five cards are of the same suit, and a five-of-a-kind is a hand where all five cards are of the same value. A joker may stand in for any card of any value or suit you like. The order of cards in your hand is irrelevant.

(a) How many hands are there where you can get a flush?

(b) How many hands are there where you can get a five-of-a-kind?

(c) How many hands in total are there where you can get one of these two types?

3. (20 pts.) A Numbers Game

(a) Alice, Bob and Carol have a sack of 10 balls, numbered 1 through 10. Each of them in turn picks one ball uniformly at random from the sack, notes its number, and then replaces it. Write down the probability space for this game, and compute the probability that none of them picks a ball numbered higher than 6.

(b) Now suppose they play the same game except that they do not return the balls to the sack after they pick them. What is the new probability space, and how does the probability of the event in part (a) change?

4. (20 pts.) Project groups

A class of 40 students is divided randomly into ten project groups of four students each.

(a) What is the size of the sample space, i.e., in how many ways can 40 people be divided into ten groups of four (without regard to the labeling of the groups)? You may leave your answer as a ratio of factorials.

(b) The class contains exactly ten Math majors. Assuming that all divisions into groups are equally likely, what is the probability that all ten of them end up in different groups?

(c) Three friends would all like to be in the same group. What is the probability that this happy event occurs?

5. (20 pts.) Necklaces

A child assembles a necklace at random from a total of 100 beads, 60 of which are red and 40 green. All possible arrangements are equally likely.

(a) What is the size of the sample space? [You may leave your answer as a binomial coefficient \binom{n}{k} for suitable n and k. Remember to justify your answer.]

(b) [This part will be useful in part (c) below.] Suppose m indistinguishable balls are thrown into n bins. We have seen that the number of distinct outcomes is \binom{n+m−1}{n−1}. What is the number of outcomes in which every bin receives at least one ball? Again, remember to justify your answer.

(c) Returning to the necklace problem, a run is a maximal contiguous sequence of beads of one color. (We assume that the necklace is open, so a run is not allowed to extend across the ends of the necklace.) Note that if the number of red runs is k, then the number of green runs must be k, k − 1 or k + 1. For any k, what is the probability that there are exactly k red runs and exactly k green runs? [You may leave your answer as a ratio of binomial coefficients. Hint: Use part (b).]