[SOLVED] MATH 127 Sample Final Exam AR

MATH 127: Sample Final Exam A

1.  The following symbolic statement describes an important mathematical theorem:

∀X ∈ P(N), (X ≠ ∅ → ∃x ∈ X,∀y ∈ X, x ≤ y).

(a) What is the name of the theorem represented by this statement?                                        [2 pts] (b) Write the logical negation of the given statement in maximally negated form.                   [5 pts]

2.  Define a function f : R → Z by f(x) = ⌊x⌋ and a function g : Z → N by

(a) Write Img◦f  ({1, √2, 5, −3.5}) in roster notation.                                                                  [4 pts]

(b)  Determine whether PreImf({0, 1}) is countable or uncountable.   Justify your answer with a sentence or two.                    [4 pts]

3.  Let  a1 , a2 , . . . , a9   ∈ Z+ , none of which has a prime factor greater than 5.  Prove that there must exist i,j ∈ [9] such that i ≠ j and the product aiaj  is a perfect square.             [8 pts]

4.  For the following problems, provide  an appropriate counting argument to justify your answer.

You may leave  answers  as products, sums  of integers, factorials,  or binomial coefficients.

You have a large bag of M&M’s consisting of the standard 6 colors:  Blue,  Brown,  Green, Orange,  Red,  and Yellow.   The  M&M’s  are  indistinguishable  except  by  color.   You  may assume an unlimited amount of each color.

(a) In how many different ways can you grab 15 M&M’s from the bag?                                    [3 pts]

(b) Use the Principle of Inclusion/Exclusion to determine the number of ways in which you can grab 15 M&M’s such that you don’t have more than 4 of any given color.                   [6 pts]

(c) After reaching into the bag, you end up with 4 Blue, 4 Orange, 3 Brown, 2 Yellow, 1 Red, and 1 Green. In how many different ways can you put these 15 M&M’s in a line?  (Remember that the M&M’s  are  only  distinguishable  by  color.)          [6 pts]

5. Let F = {f : N → N | f is a function}. Define a relation ~ on F by

f ~ g ⇐⇒ |{i ∈ N | f(i) g(i)}|  < N0 .

(a)  Prove that ~ is an equivalence relation on F.                                                                       [12 pts]

(b)  Given two functions f, g ∈ F, we define their sum, f + g, as the function f + g : N → N such that (f + g)(n) = f(n) + g(n).  Assume that f1 , f2 , g1 , g2  ∈ F such that f1  ~ f2 and g1  ~ g2 . Prove that f1 + g1  ~ f2 + g2 .       [6 pts]

6. Let n ∈ N. Prove that

using a “counting in two ways” argument.                                                                                     [12 pts]

● Use the exact form of the equation as given; do not simplify it algebraically.

● If your argument involves constructing partitions, justify that your construction defines a valid partition.

7. Let n be an arbitrary and fixed odd integer.  Prove that the following congruence holds for all integers k ≥ 3:                                                     [10 pts]

n(2k−2) ≡ 1    (mod 2k )

8. Let S = {n ∈ Z | n ≡ 1  (mod 7)}.  Prove that |S| = |N| by explicitly constructing a bijection between S and N, and proving that it is a bijection.

Do not use the Cantor-Bernstein-Schr¨oder (CBS) Theorem.

You do not need to prove that your function is  well-defined,  but ill-defined functions  will lose the majority of points.       [12 pts]

9. Let a and b be coprime integers. Prove that there exist x,y ∈ Z such that

(a3 b2 )x + (a + b)y = 1.

[10 pts]