Challenging Math Questions – Solutions Last week I gave you some challenging math questions to work on. Click the following link to see last week’s post: Some Challenging Mathematics To Raise Mathematical Maturity Today I will provide solutions to each of those questions. Warm-up Exercises Recall that a set B is a subset of a set A if every element of B is an element of A. For example, if A = {1,2,3,4,5,6} and B = {4,5,6}, then B is a subset of A. Also { } is the emptyset, the unique set consisting of no elements. How many subsets does { } have? List them. { } is a subset of every set. In particular, { } is a subset of itself. This is the only subset of { }. So { } has 1 subset, namely { }. (Note that 1 = 20) How many subsets does {1} have? List them. {1} has 2 subsets: { } and {1}. (Note that 2 = 21) List the subsets of {1, 2}, {1, 2, 3}, and {1, 2, 3, 4}. {1, 2} has 4 subsets. They are { } , {1}, {2}, and {1,2}. (Note that 4 = 22) {1, 2, 3} has 8 subsets: { } , {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, and {1,2,3}. (Note that 8 = 23) {1, 2, 3, 4} has 16 subsets: { } , {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, and {1,2,3, 4}. (Note that 16 = 24) How many subsets does the set {1, 2, 3, 4, 5, 6, 7, 8} have? Following the pattern in the previous examples {1, 2, 3, 4, 5, 6, 7, 8} has 28 = 256 subsets. How many subsets does the set {1,…, n} have where n is a positive integer. {1,…,n} has 2n subsets. Theoretical Exercise Give a proof of the result from problem 5. Solution by Mathematical Induction: The base case is problem 1. For the inductive step, suppose that every set A with k elements has 2k subsets. Let B be a set with k+1 elements, and let x be any element of B. By assumption there are 2k subsets of B that do not contain x, and 2n subsets of B that do contain x, for a total of 2k+ 2k = 2(2k) = 2k+1 subsets. By the Principle of Mathematical Induction {1,…,n} has 2n subsets for all integers n ≥ 0. Remarks: (i) The Principle of Mathematical Induction says that if a statement is true for n = 0, and the truth of the statement for k implies the truth for k + 1, then the statement is true for all integers n ≥ 0. (ii) Note that the lists chosen in problems 2 and 3 emulate the proof given here. Solution by counting: There are nCk subsets of {1,…, n} with k elements. So all together there are nC0 + nC1 +…+ nCn= (1 + 1)n = 2n subsets of {1,…, n}. Remarks: (i) nCk means the number of combinations of n things taken k at a time. In a combination order does not matter (as opposed to the permutation nPk where the order does matter). nCk = n!/[k!(n – k)!] We don’t actually need to do any of these computations for this problem. (ii) Here we have used the Binomial Theorem with x = y = 1: (x + y)n = nC0 xny0 + nC1 xn-1y1 +…+ nCn-1 x1yn-1 + nCn x0yn (1 + 1)n = nC0 1n10 + nC1 1n-111 +…+ nCn-1 111n-1 + nCn 101n 2n = nC0 + nC1 +…+ nCn-1 + nCn Advanced Exercises Recall that a set is selfish if the number of elements it has is in the set. For example, X10 = {1,2,3,4,5,6,7,8,9,10} is selfish because it has 10 elements, and 10 is in the set. A selfish set is minimal if none of its proper subsets is also selfish. For example, the set X10 is not a minimal selfish set because {1} is a selfish subset. Let Xn = {1,…,n}. How many selfish subsets does Xn have where n is a positive integer? Let’s start with some simple examples. X1 = {1} has 1 selfish subset, namely {1} itself. The selfish subsets of X2 = {1,2} are {1} and {1,2}, so that X2 has 2 selfish subsets. The selfish subsets of X3 = {1,2,3} are {1}, {1,2}, {2,3}, and {1,2,3}, so that X3 has 4 selfish subsets. The selfish subsets of X4 = {1,2,3,4} are {1}, {1,2}, {2,3}, {1,2,3}, {2,4}, {1,3,4}, {2,3,4} and {1,2,3,4}, so that X4 has 8 selfish subsets. In general, it looks like Xn has 2n-1 selfish subsets. To see this, note that there are n-1Ck-1 selfish subsets of {1,…,n} with k elements (we must choose k, and then we choose k – 1 elements from the remaining n – 1 elements). So all together there are n-1C0 + n-1C1 +…+ n-1Cn-1 = (1 + 1)n-1 = 2n-1 selfish subsets of {1,…,n}. List the minimal selfish subsets of Xn for n = 1, 2, 3, 4, 5, and 6. X1 has 1 minimal selfish subset, namely {1}. X2 has 1 minimal selfish subsets, namely {1}. (Note that {1,2} is selfish, but not minimal because {1} is a selfish subset.) X3 has 2 minimal selfish subsets, namely { 1} and {2,3}. X4 has 3 minimal selfish subsets, namely {1}, {2,3}, and {2,4}. X5 has 5 minimal selfish subsets. They are {1}, {2,3}, {2,4}, {2,5}, and {3,4,5}. X6 has 8 minimal selfish subsets. They are {1}, {2,3}, {2,4}, {2,5}, {3,4,5}, {2,6}, {3,4,6}, and {3,5,6}. How many minimal selfish subsets does X10 have? Following the pattern, it looks like X7 has 8 + 5 = 13 minimal selfish subsets, X8 has 13 + 8 = 21, X9 has 21 + 13 = 34, and X10 has 34 + 21 = 55 minimal selfish subsets. In terms of n, how many minimal selfish subsets does the set Xn have? Xn has fn minimal selfish subsets where fn is the nth term of the Fibonacci sequence. Remark: The Fibonacci sequence is the sequence fn = fn-1 + fn-2, f1 = f2 = 1. The first few terms of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Give a proof of the result from problem 10. We will prove this by the Principle of Strong Induction on n, with the base case of n = 1 and n = 2 already complete. Assume that k > 2 and that Xr has fr minimal selfish subsets for each r < k. Each minimal selfish subset of Xk-1 is a minimal selfish subset of Xk, and if A is a minimal selfish subset of Xk-2, then the set A’ formed by adding 1 to each element of A, and throwing in k, is a minimal selfish subset of Xk. This yields fk-1 + fk-2 = fk minimal selfish subsets of Xk. Conversely, note that if a minimal selfish subset of Xk does not contain k, then it is a minimal selfish subset of Xk-1, and if a minimal selfish subset of Xk does contain k, then if we delete k and subtract 1 from each of the remaining elements we get a minimal selfish subset of Xk-2. Thus there are exactly fk minimal selfish subsets of Xk. Remark: The Principle of Strong Induction says that if a statement is true for n = 0 (or more generally n = m), and the truth of the statement for all r < k implies the truth for k, then the statement is true for all integers n ≥ 0 (or more generally n ≥ m). If you liked this article, please share it with your Facebook friends: If you would like to begin learning more advanced mathematics, check out my math books Pure Mathematics for Beginners, Set Theory for Beginners, and Topology for Beginners. These books contain no prerequisites and are perfect for anyone just starting out in theoretical math. You can get them all for one low price by clicking on the image below. Comments comments