TOC CHapter 1 Problems

Problems and Solutions

Problem 1	It is known that at the university 60 percent of the professors play tennis, 50 percent of them play bridge, 70 percent jog, 20 percent play tennis and bridge, 30 percent play tennis and jog, and 40 percent play bridge and jog. If someone claimed that 20 percent of the professors jog and play bridge and tennis, would you believe this claim? why?
Solution.	Let T denote the percentage of professors who play tennis. Let B denote the percentage of professors who play bridge. Let J denote the percentage of professors who jog. Given that |T| = 60, |B| = 50, |J| = 70, |T ∩ B| = 20, |T ∩ J| = 30, |B ∩ J| = 40. |T ∩ B ∩ J| = |T ∪ B ∪ J| − |T| − |B| − |J| + |T ∩ B| + |T ∩ J| + |B ∩ J|. |T ∩ B ∩ J| = 100 − 60 − 50 − 70 + 20 + 30 + 40 = 10. Given claim is wrong.
Problem 2	Use mathematical induction to prove for all positive integers n, n(n2 + 5) is an integer multiple of 6.
Solution.	Base: n = 1, 1(1 + 5) = 6, is an integer multiple of 6. Hypothesis: Let us assume that it is true for n. Induction Step: We need to prove that it is true for n + 1. Consider . By hypothesis we know that n(n2 + 5) is divisible by 6. Clearly the last expression is divisible by 6. Therefore for all n, n(n2 + 5) is an integer multiple of 6.
Problem 3	Suppose that we have a system of currency that has $3 and $5 bills. Show that any debt of $n can be paid with only $3 and $5 bills for each integer n ≥ 8. Do the same problem for $2 and $7 bills and n ≥ 9.
Solution.	Base: n = 8, clearly it can be paid with $3 and $5 bills. Hypothesis: Assume that debt of $n can be with $3 and $5 bills. Induction Step: Consider a debt of $n + 1. Let n = 3k1 + 5k2 If k1 ≥ 3, then n + 1 = (k1 − 3) 3 + (k2 + 2) 5. If k1 = 2, then n + 1 = 4 × 3 + (k2−1) 5. If k1 = 1, then n + 1 = 3 × 3 + (k2 − 1) 5. If k1 = 0, then n + 1 = 2 × 3 + (k2 − 1) 5. (Note that k2 ≥ 1 in cases 2, 3 and 4 as we need to prove only for n ≥ 8.) Hence n + 1 = k3. 3 + k4. 5 where k3 and k4 are integers. Hence the result.
Problem 4	Let A be a set with n distinct elements. How many different binary relations on A are there? How many of them are reflexive? How many of them are symmetric? How many of them are reflexive and symmetric? How many of them are total ordering relation?
Solution.	There are n2 elements in the cross product A × A. Since relation is a subset of cross product, the number of different binary relations on A are 2n2. There are 2n2−n reflexive relations. There are 2n(n+1)/2 symmetric relations. There are relations which are both reflexive and symmetric. There are n! total ordering relations.
Problem 5	Let R be a symmetric and transitive relation on set A. Show that if for every ‘a’ in A there exists ‘b’ in A, such that (a, b) is in R, then R is an equivalence relation.
Solution.	Given that R is a symmetric and transitive relation on A. To prove that R is an equivalence relation, we need to prove that R is reflexive. By hypothesis we know that ∀a∃b(a, b ∊ A ∧ (a, b) ∊ R). Since R is symmetric, it follows that if (a, b) ∊ R then (b, a) ∊ R. Also given that R is transitive, it follows that (a, a) ∊ R. This implies that ∀a∊A, (a, a) ∊ R. This proves that R is reflexive. Therefore, R is an equivalence relation.