Quiz 6         MAT 118, Spring 2003

1. Find the probability that if I draw 5 cards from a standard deck of 52 cards, there will be no pairs. (You need not multiply it out, but you can if you like.)

Solution: First, notice that no pairs'' is the same as saying all the cards have different numbers''. So, we need to count how many ways we can pick 5 cards from a deck, all with different numbers. It is easiest if we view our hand as being ordered- that is, we distinguish the order in which we pick the cards.

First we pick the first card. There are 52 choices for this card.

For the second card, we have only 48 choices, since we cannot pick any cards which are the same number as the first.

For the third card, we have 44 choices: we can't use the 4 cards that are the same number as the first card, nor the same number as the second.

Continuing in this way, we see that there are ways to pick 5 cards with no pairs, paying attention to which is first. (If we wanted to ignore the order, we would divide by ).

Since there are different ways to pick 5 cards, the probability of no pairs is

This is a probability of just over half, about .

2. The city of Glorpton is divided by the River Glorp, and has 5 bouroughs: Northton, Southford, Pig Island, Grub Isle, and Dink. There are nine bridges, as shown in the figure below.

Is it possible to devise a path through Glorpton that crosses each bridge exactly once? You need not start and finish at the same place.

If your answer is yes, show your solution. If no, give a reason why it cannot be done.

Solution: The graph for this situation is shown on the left below; we replace each place by a vertex, and put in an edge if there is a bridge between two places.

Since the vertices for Southford and Dink have three edges (an odd number) from themand all the others have four (an even number), there is an Eulerian path. Such a path must either start or end in Southford, and end or start on Dink. One such solution is shown on the right above.

Scott Sutherland 2003-04-05