MOE H3 Math Proofs and Reasoning Problem Set 4

MOE H3 Math Mathematical Proofs and Reasoning Problem Set 4 1. Show that there exists integers x and y that satisfy (2n + 1)x + (9n + 4)y = 1 for every integer n. 2. Prove that for every pair of irrational numbers p and q such that p < q, there is an irrational x such that p < x < q. 3. Show that there is one and only one integer t such that t, t+2, t+4 are all prime numbers. 4. Given n real numbers a1, a2, . . . , an. Show that there exists an ai (1 ≤ i ≤ n) such that ai is greater than or equal to the mean (average) value of the n numbers. 5. Prove that there are infinitely many prime numbers that are congruent to 3 modulo 4. 6. Prove that, for any positive integer n, there is a perfect square m2 (m is an integer) such that n ≤ m2 ≤ 2n. 7. (Y2022 Q3) For any real number s, the greatest integer less than or equal to s is denoted by ⌊s⌋. For example, ⌊3.7⌋ = 3 and ⌊5⌋ = 5. (a) For any positive integer a and real number t, it is given that t can be written as an + p, where n is an integer and a > p≥ 0. Prove that Z a 0 x + t a

dx = t. (b) For any positive integer a and b and real number x (i) prove that  j x a k b  = j x ab k , (ii) find Z ab 0 (f g(x) − gf (x))dx where f (x) = x + a b

and g(x) = x + b a

. 8. (Y2024 Q7) Let S = {1, 2, ...,50} and let D be a subset of S of size 27.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 (a) Show that there are 25 subsets of S of the form {a, a+ 5} whose union is S. Apply the pigeonhole principle to prove that D must contain two numbers that differ by exactly 5. (b) Prove that D must contain two numbers that differ by exactly 6. Show that D does not necessarily contain two numbers that differ by exactly 7. (c) Determine the maximum possible size of a subset of S that contains no four con- secutive numbers. (d) Determine the maximum possible size of a subset of S that contains no two numbers whose sum is a multiple of 10. 9. A function f : X → Y is said to be injective if ∀x1, x2 ∈ X, f (x1) = f (x2) = ⇒ x1 = x2. A function f : X → Y is said to be surjective if ∀y ∈ Y, ∃x ∈ X such that f (x) = y. Use the pigeonhole principle and proof by contradiction to prove: given nonempty finite sets X and Y with |X| = |Y |, a function f : X → Y is injective if and only if it is surjective. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 Hints 1. Hint for Question 1. Since this is must be true for all n, compare coefficients of n. 2. Hint for Question 3. Existence part is by construction; uniqueness part: show that one of t, t+ 2, t+ 4 must be divisible by 3. 3. Hint for Question 4. Prove by contradiction by assuming all the n numbers are less than the average value. 4. Hint for Question 5. The idea is similar to the proof for infinitely many primes. Use the fact that integers of the form 4 k + 1 are closed under multiplication. 5. Hint for Question 6. Prove by contradiction. 6. Hint for Question 7. For part (b), write x = kab + r for some integer k and 0 ≤ r < ab. Page 3