Spring 2008

Be neat and organized. Clearly indicate your answers. 100 points possible.

Part I - Computational Problems - 50 pts.

1. (10 pts.) Compute 17¹⁶ mod 35. Use an ordinary calculator for the arithmetic; support your answer with enough work to show you know what you're doing.

2. (10 pts.) Let A={1,2,3} and B={3,6,9}.

Let C=A×P(B). How many elements are in P(C)?

3. (10 pts.) Let Z^nonneg={0,1,2,3,...}. Let S be the set of all strings of a's, b's, and c's.

Define F:S® Z^nonneg by letting F(s)= the number of c's in s, for all s Î S.

Define G: Z^nonneg® Z^nonneg by letting G(n)=n², for all n Î Z^nonneg.

Define H:S® Z^nonneg by letting H=G°F.

(a) Find H(aaba).

(b) Is H one-to-one? Briefly explain your reasoning, or give a counterexample.

(c) Is H onto? Briefly explain your reasoning, or give a counterexample.

4. (10 pts.) Let R be the relation on A={1,2,3,4,5} defined by

R={(1,1),(1,5),(2,2),(3,3),(3,4),(4,3),(5,1)}.

Is R reflexive? symmetric? transitive? Briefly explain your reasoning, or give counterexamples.

5. (10 pts.) Eight points labeled A, B, C, D, E, F, G, H are arranged in a plane in such a way that no three lie on the same straight line. A triangle will be formed having three of the labeled points as vertices.

How many such triangles do not have B as a vertex?

Part II - Proofs - 50 pts.

Do three of these four problems.

6. (16.66... pts.) Use regular mathematical induction to prove that 5²ⁿ-1 is divisible by 24, for all integers n ³ 1.

7. (16.66... pts.) Let c₀=2, c₁=8, and for integers n > 1 let c_n=8c_n-1-15c_n-2.

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

8. (16.66... pts.) Let D and E be sets. Prove by contradiction that if E Í D, then D^cÇE=Æ.

9. (16.66... pts.) Let f:X® Y, A Í Y, and B Í Y.

Prove f^-1(AÇB) Í f^-1(A)Çf^-1(B).