MOE H3 Math Proofs and Reasoning Problem Set 4 Solutions

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. Solution: By constructive proof. Take x = 9 and y = −2. We check: (2n + 1) × 9 + (9n + 4) × (−2) = (18n + 9) + (−18n − 8) = 1 for any n. Hence x = 9 and y = −2 provide a pair of solution to this equation. 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. Solution: Consider the average of p and q: p <p + q 2 < q. If p + q 2 is irrational, take x = p + q 2 and we are done. If p + q 2 is a rational number r, take the average of p and r: p <p + r 2 < r < q. Since p is irrational and r is rational, so p + r 2 is irrational (this can be proven by contradiction). In this case, we take x = p + y 2 . 3. Show that there is one and only one integer t such that t, t+2, t+4 are all prime numbers. Solution: Existence: By construction, take t = 3. Then 3 , 5, 7 are all prime numbers. Uniqueness: Suppose s, s+ 2, s+ 4 are all primes, and s >3. There are two cases: (i) s ≡ 1 mod 3 and (ii) s ≡ 2 mod 3. For case (i), s + 2 ≡ 3 ≡ 0 mod 3 which means 3 | s + 2. So s + 2 is not a prime, which is a contradiction. For case (ii), s + 4 ≡ 6 ≡ 0 mod 3 which means 3 | s + 4. So s + 4 is not a prime, which is a contradiction. Hence, it is not possible to find another triplet s, s+ 2, s+ 4 which 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.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 Solution: By contradiction. Let ¯a denote the mean value of the n given numbers. Suppose ai < ¯a for all ai. Then ¯a = a1 + a2 + · · ·+ an n < ¯a + ¯a + · · ·+ ¯a n = n¯a n = ¯a. We derive ¯a <¯a, which is a contradiction. So there must be some ai such that ai ≥ ¯a. 5. Prove that there are infinitely many prime numbers that are congruent to 3 modulo 4. Solution: Use a proof by contradiction. Suppose there are only finitely many primes that are congruent to 3 modulo 4. Let p1, p2, . . . , pm be the list of all the primes that are congruent to 3 modulo 4. We construct an integer M by M = (p1p2 . . . pm)2 + 2. We have the following observation: (i) M ≡ 3 mod 4. (ii) Every pi divides M − 2. (iii) None of the pi divides M . [Otherwise, together with (ii), this will imply pi divides 2, which is impossible.] (iv) M is not a prime number. [Otherwise, by (i), M is a prime number congruent to 3 modulo 4. But M ̸= pi for all 1 ≤ i ≤ m. This contradicts to the assumption that p1, p2, . . . , pm are all the prime numbers congruent to 3 modulo 4.] From the above discussion, we know that M is a composite number by (iv). So it has a prime factorization M = q1q2 · · ·qk. Since M is odd, all these prime factors qj must be odd, and hence qj must be congruent to either 1 or 3 modulo 4. By (iii), qj cannot be any of the pi. So all qj must be congruent to 1 modulo 4. Then M , which is the product of qj, must also be congruent to 1 modulo 4. This contradicts (i) that M is congruent to 3 modulo 4. Hence we conclude that there must be infinitely many primes 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. Solution: By contradiction. Suppose there is a positive integer n such that for all perfect squares m2, we either have m2 < nor 2n < m2. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 Take an integer m0 such that m2 0 < nand (m0 + 1)2 > 2n. i.e. m2 0 is the largest square smaller than n while (m0 + 1)2 is the smallest square larger than 2 n. By combining these two inequalities, we have m2 0 + 2m0 + 1 > 2n >2m2 0 (∗) Comparing the leftmost term and rightmost term in ( ∗), we have 2 > m2 0 − 2m0 + 1 = (m0 − 1)2 which is impossible except for m0 = 0, 1 and 2. If m0 = 0, then by ( ∗), 1 > 2n >0, which is impossible, as there is no integer between 0 and 1. If m0 = 1, then by ( ∗), 4 > 2n > 2, which is impossible, as there is no even integer between 2 and 4. If m0 = 2, then by ( ∗), 9 > 2n >8, which is impossible, as there is no integer between 8 and 9. So it is not possible to find a positive integer n such that for all perfect squares m2, we either have m2 < nor 2n < m2. Hence we conclude that, for any positive integer n, there is a perfect square m2 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. Solution: First note that if −1 < s <1, then for integer n, ⌊n + s⌋ = n + ⌊s⌋. Also, if 0 < c <1, then Z 1+c c ⌊x⌋dx = c as the graph is the constant 0 graph on (c, 1) and the constant 1 on (1, 1+ c). Hence, the integral, which is the area of a rectangle with breath ((1 + c) − c) and height 1, is equal to ((1 + c) − c) × 1 = c. So, Z a 0 x + t a

dx = Z a 0 x + an + p a

dx = Z a 0 x + p a + n

dx = Z a 0 x + p a

+ n dx= na + Z a 0 x + p a

dx Page 3

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 Perform change of variable s = x + p a , we have Z a 0 x + p a

dx = Z 1+ p a p a ⌊s⌋a ds= a p a

= p. Hence, Z a 0 x + t a

dx = na + +p = 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 , Solution: Write x = kab + r for some integer k and 0 ≤ r < ab. Thenj x ab k = kab + r ab

= k. On the other hand,  j x a k b  =  abk + r a

b  =  bk + j r a k b  = k +  j r a k b  . Now since 0 ≤ r < ab, 0 ≤ r a < b, and hence 0 ≤ j r a k < b, and so,  j r a k b  = 0. Hence,  j x a k b  = k = 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

. Solution: f g(x) =  x + b a

+ a b  =  x + b a + a

b  = x + b + a2 ab

Page 4

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 where the third equality follows from (i). Then by (a), Z ab 0 f g(x) dx = Z ab 0 x + b + a2 ab

dx = Z ab 0 x + (b + a2) ab

dx = b + a2. Similarly, gf (x) = x + a + b2 ab

and so Z ab 0 gf (x) dx = Z ab 0 x + (a + b2) ab

dx = a + b2. Hence, Z ab 0 (f g(x) − gf (x))dx = Z ab 0 f g(x) dx − Z ab 0 gf (x) dx = b + a2 − a − b2 = ( a − b)(a + b − 1). 8. (Y2024 Q7) Let S = {1, 2, ...,50} and let D be a subset of S of size 27. (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. Solution: Let aij = 10(i − 1) + j, for i = 1, 2, ...,5 and j = 1, 2, ..,5. Then it is clear that {ai1j1, ai1j1 + 5} ∩ {ai2j2, ai2j2 + 5} = ∅ if (i1, j1) ̸= (i2, j2), and that n[ i,j=1 {aij, aij + 5} = S. By pigeon hole principle, since D contains 27 numbers, it must be that there is a i, j= 1, ...,5 such that {aij, aij + 5} ⊆D (for otherwise, D only contain at most 1 from each of the set {aij, aij + 5}, and thus it can at most have 25 numbers). (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. Solution: Let aij = 12(i − 1) + j, for i = 1, 2, ...,4, j = 1, 2, ...,6. Then [ i = 1, 2, ...,4 j = 1, 2, ...,6 {aij, aij + 6} ∪ {49} ∪ {50} = S. There are a total of 26 sets. So, by pigeon hole principle, there must be a i, jsuch that {aij, aij + 6} ⊆D. The set D = {1, 2, ...,7, 15, 16, ...,21, 29, 30, ...,35 43, 44, ...,48} Page 5

H3 Math (Mathematical Proofs and Reasoning) Problem Set 4 contains 27 numbers but no two of them differ by exactly 7. (c) Determine the maximum possible size of a subset of S that contains no four con- secutive numbers. Solution: Divide S into blocks of 4, {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11,