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]