MOE H3 Math Proofs and Reasoning Problem Set 5

MOE H3 Math Mathematical Proofs and Reasoning Problem Set 5 1. Of the 182 students who are taking three first year core Mathematics modules (Rea- soning, Algebra and Calculus), 129 like Reasoning, 129 like Algebra, 129 like Calculus, 85 like Reasoning and Algebra, 89 like Reasoning and Calculus, 86 like Algebra and Calculus, and 54 like all three modules. How many of the students like none of the core modules? 2. Distributive law: 1. X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z), 2. X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z). Use the distributive law to prove that (A ∩ B) ∪ (B ∩ C) ∪ (C ∩ A) = (A ∪ B) ∩ (B ∪ C) ∩ (C ∪ A). 3. Given sets A, B⊂ X, their symmetric difference is A△B = ( A \ B) ∪ (B \ A) = ( A ∪ B) \ (A ∩ B). Prove that (a) the symmetric difference is associative: ( A△B)△C = A△(B△C) for all A, B, C⊆ X; (b) there exists a unique N ∈ P(X) such that A△N = A for all A ⊆ X; (c) for each A ⊆ X, there exists a unique A′ ⊆ X such that A△A′ = N ; (d) for each A, B⊆ X, there exists a unique C ⊆ X such that A△C = B. 4. Use the inclusion–exclusion principle to prove that the number of surjections{1, 2, ..., m} → {1, 2, ..., n} is given by nm − n 1

(n − 1)m + n 2

(n − 2)m − · · ·+ (−1)n−1 n n − 1

1m. Deduce that nn − n 1

(n − 1)n + n 2

(n − 2)n − · · ·+ (−1)n−1 n n − 1

1n = n!. 5. Use the pigeonhole principle to prove that, given ten distinct positive integers less than 107, there exist two disjoint subsets with the same sum. 6. Let a, b, cbe fixed positive integers. Find and correct the error(s) in the proof of the statement:

H3 Math (Mathematical Proofs and Reasoning) Problem Set 5 If a divides b and a divides c, then a divides b + c. Proof. Assume a divides b and a divides c; we must prove a divides b + c. We have assumed there exists an integer k with b = ak. We have also assumed there is an integer k with c = ak. We must prove there exists m ∈ Z such that b + c = am. Choose m = 2k, which is an integer. Use the assumptions to compute b + c = ak + ak = a(2k) = am, as needed. 7. Let a and b be fixed nonzero integers. Find and correct the error(s) in the proof of the statement: If a divides b and b divides a then b = ±a. Proof. Assume a | b and b | a. By assumption, there is an integer c with b = ca and a = cb. By substitution, a = cb = c(ca) = c2a. Since a ̸= 0, we can divide by a to get c2 = 1. Then c = 1 or c = −1, hence b = a or b = −a. 8. (Adapted from IMO 1964, Day 2) A complete graph with n vertices, denoted by Kn, consists of n distinct vertices (points or nodes) such that each vertex is connected to every other vertex by an edge (a line segment joining two distinct vertices). It is a well-known result in graph theory that any 2-coloring of the edges of K6 (that is, coloring each edge with one of two colors) necessarily contains a monochromatic triangle — a set of three vertices all connected to each other by edges of the same color. Using this fact, we can solve the following problem: Seventeen people correspond by mail with one another, each one with all the rest. In their letters, only three different topics are discussed. Each pair of correspondents discusses only one of these topics. Prove that there are at least three people who write to each other about the same topic. (a) Using the Pigeonhole Principle, prove that any 2-coloring ofK6 contains a monochro- matic triangle. (b) Deduce that among seventeen people, there must exist three who correspond with each other about the same topic. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 5 Hints 1. Hint for Question 1. Use Inclusion-Exclusion Priciple. 2. Hint for Question 4. For eachi ∈ {1, 2, ..., n}, let Ai = {f : Nm → Nn | i is not a value of f }. Use Inclusion-Exclusion Principle. 3. Hint for Question 5. Let the ten distinct positive integers be a1, a2, . . . , a10, 1 ≤ ai < 107. Show that 10X i=1 ai ≤ 1, 015. 4. Hint for Question 8. For (b), this is a 3-coloring of edges of K17. Consider one of the vertex, and reduce the problem to a 2-coloring of edges of K6. Page 3