Exam 2

Show all work in a neat and organized fashion. Clearly indicate your answers.

100 points possible.

1. (20 pts.) (a) Let R be a relation defined on a set A. Define each of the following. The first one is done for you.

R is reflexive: "x Î A, x R x

R is irreflexive:

R is symmetric:

R is antisymmetric:

R is transitive:

(b) Consider the relation Í on 2 ^Z (i.e., the ``is-a-subset-of'' relation defined on all sets of integers). Which of the five properties from part (a) does Í have? (No proof or disproof required.)

2. (10 pts.) For each equivalence relation, find the requested equivalence class.

(a) R={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)} on {1,2,3,4}. Find [1].

(b) R is ``has-the-same-tens-digit-as'' on the set {x Î Z : 200 < x < 400}. Find [234].

3. (10 pts.) How many different anagrams (including nonsensical words) can be made from IRREGULARITIES?

(b) How many different anagrams (including nonsensical words) can be made from IRREGULARITIES, given that the first letter must be a vowel and that the letters must alternate vowel-consonant-vowel-consonant-etc.?

4. (10 pts.) A standard deck of 52 cards contains 4 different suits, with 13 different ranks in each suit. A poker hand consists of 5 cards chosen from a standard deck.

(a) A poker hand is called ``three of a kind'' provided it contains three cards of the same rank, with two other cards having two other different ranks. How many three of a kind hands are there?

(b) Define a poker hand to be a ``four flush'' provided it contains exactly four cards of the same suit. (Note: by this definition, a four flush hand may or may not contain a pair, and it may or may not be a straight.) Using this definition, how many four flush hands are there?

5. (10 pts.) Write the contrapositive of each statement. (Do not prove!)

(a) If p is prime, then 2^p-2 is divisible by p.

(b) If c is an odd integer, then the equation n²+n-c=0 has no integer solution for n.

6. (15 pts.) Prove the following statement by induction.

(1-[1/4])(1-[1/9])...(1-[1/(n2)])=[(n+1)/2n]       for all integers n ³ 2

7. (15 pts.) Let b₀=2, b₁=7, and for integers n > 1 let b_n=7b_n-1-10b_n-2.

What are b₂ and b₃?

Prove, using strong induction, that b_n=2ⁿ+5ⁿ for all integers n ³ 0.

8. (10 pts.) Let A={1,2} and B={3,4,5}. Write down all functions f:A® B. Indicate which are one-to-one and which are onto B.