This is an open-book, open-notes, open-computer, and open-Internet exam. It is an exam, however, so limit your discussion of it to conversations with Jeff Ondich. Explain your answers clearly.

This exam has been formatted in HTML, which is not especially good at displaying mathematical notation. Where appropriate, I have used C++ style notation. Where C++ has no equivalent symbol, I have used functional notation (e.g. using Floor(N/3) to represent the floor of N divided by 3). If you have questions about any of the notaion on this exam, please let me know.

1. (8 points) Consider the statements:
   • P ==> Q (I'll refer to this one as S)
   • P ==> not Q
   • not P ==> Q
   • not P ==> not Q
   • Q ==> P
   • Q ==> not P
   • not Q ==> P
   • not Q ==> not P

   Do the following:

   • Which statement is the converse of S? Which is the contrapositive of S?
   • If S is true, which (if any) of the other statements is guaranteed to be true?
   • If S is true, which (if any) of the other statements is guaranteed to be false?
   • Is it possible to select P and Q in such a way that all the statements above are true? If so, what P and Q work? If not, why not?

2. (8 points) Let A and B be subsets of U. Show that Union( Complement(A), B ) equals Complement( Intersection( A, Complement(B) ) ) in three different ways:
   • Using Venn diagrams
   • Using one of DeMorgan's Laws
   • Showing that x is in Union( Complement(A), B ) if and only if x is in Complement( Intersection( A, Complement(B) ) ).

3. (8 points) Let P be the set of all people who have ever lived. Let M : P --> P be the function defined by M(x) = the biological mother of x.
   • Is M one-to-one? Why or why not?
   • Is M onto? Why or why not?
   • What is the meaning of the function M o M (that is, the functional composition of M with itself)?
   • Is M invertible? Why or why not?

4. (8 points) For which integer values of N is 2^N > N^2? Prove your answer by induction.

5. (8 points) Consider once again the collection of 5-card poker hands.
   • How many different straight flushes are there? (A straight flush is a straight, all of whose cards are the same suit. For example, the hand 4H 5H 6H 7H 8H is a straight flush.)
   • How many 1-pair hands are there? (A 1-pair hand has two cards with the same value, and no other cards whose values match. For example, 4H 4C JS 9D 3C is a 1-pair hand, but 4H 4C JS JH 3C is not.)

6. (3 points) I'd like to listen to some music I haven't listened to before. What do you think I should try?

7. (8 points) Let's recap the Art Gallery Theorem discussion. Consider an N-sided simple polygon P (where "simple" means that the polygon has no holes). A point A can "see" a point B if the straight line segment connecting A and B is entirely inside P. The Art Gallery Theorem says that for any N-sided simple polygon, it is possible to select Floor(N/3) or fewer vertices such that any point inside P can be seen by at least one of the chosen vertices. In art gallery terms, you need no more than Floor(N/3) guards to make sure the whole gallery is watched at once.

   In class and on the last homework assignment, we stepped through most of the proof of the Art Gallery Theorem. What we neglected to do, however, was discuss whether Floor(N/3) might not be too large. For example, is it possible that there is some N for which all N-sided polygons can be covered by Floor(N/4) guards? The answer is no. To see why, do the following:

   • Draw a 6-sided polygon that requires at least Floor(6/3) guards. Explain why fewer guards would not do the job.
   • Do the same for a 9-sided polygon.
   • Show how you would extend your 6-sided and 9-sided polygons to draw an N-sided polygon that requires Floor(N/3) guards, no matter how big N is.