Assignment 1 MA 375 Homework 1 Solutions Section 4.1: 50: The claim is true if n=1 because if you pick 2 numbers from the set {1,2} then it is easy to see that there are 2 chosen numbers that divide each other. (Generally, if 2 equal numbers are chosen this is true trivially, and if you choose 2 distinct ones an easy check shows that the claim is ok.) Now assume the claim is true for n+1 numbers chosen from {1,2,...,2n} and let's try to show it stays true if we pick n+2 numbers from {1,...,2n+2}. Again, if there are 2 equal numbers there is nothing to prove really, so let's suppose all the chosen numbers are distinct. If all, or just n+1 of the n+2 chosen numbers are in the smaller set {1,2,...,2n} then the inductive hypothesis helps us out to conclude that there are 2 chosen ones that divide each other. So let's consider the case where 2n+1, 2n+2 and n of the numbers {1,2,...,2n} are chosen. Clearly, if in this situation n+1 is also a chosen number we are done because n+1 divides 2n+2. So assume that n+1 is not chosen. Let C be the chosen numbers that are less than 2n+1; there are n of these. Consider the set D which is C together with the number n+1. D contains n+1 distinct numbers, and they are all in {1,2,...,2n}. By the inductive hypothesis, D contains 2 numbers A and B which divide each other. If neither A nor B are equal to n+1, then C contains both A and B and so A and B are both chosen numbers and we are done. Finally, we inspect the case where either A or B is n+1. The other number is then either a divisor or a multiple of n+1. It can't be a multiple because the smallest multiple would be 2(n+1) which is bigger than 2n+1 and hence not in C. It follows that C contains a divisor of n+1. Of course, n+1 is not a chosen number, so that this divisor does not seem to be helpful. However, 2*(n+1)=2n+2 IS a chosen number, and a divisor of n+1 is also a divisor of 2n+2. So even in this worst of all cases there are 2 chosen numbers that divide each other. This completes the inductive step and the proof. 64: If there are 2 people you can find out with 2 questions whether there is a celebrity and 2 is no more than 3(2-1)=3. Suppose now there are n+1 people. Fist ask "does A know B?" with arbitrary A, B. If "yes" then A is not a celebrity, if "no" then B is not. In either case, one person (let's call him E) has been eliminated from being one. Now by induction one can find out with at most 3(n-1) questions if there is a celebrity among the remaining n people. If there is none, there isn't one in the big set either. If there _is_ one between the n people (let's call him C), in order to confirm C as celebrity between all n+1 people, you still have to check that E knows C and that C does not know E. This uses at mot 1+3(n-1)+2=3(n+1-1) questions. 54: The proof breaks down at the point where they write a^(k+1) = a^k*a^k/a^(k-1). The equation is true, but k-1 is not necessarily a nonnegative integer, even if k is a nonnegative integer. (Specifically, if k=0, which is a nonnegative integer, then k-1=-1 is not nonnegative!) Therefore we cannot use the inductive hypothesis on -1. And so the proof fails. 8: Note that 2-2*7+2*7^2-...+2*(-7)^n = sum 2*(-7)^i i=0 Let P(n) be the statement " 2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4 ". Armed with this we see that the base case n=0 is true: (1-(-7)^1)/4 = (1+7)/4 =2. Now assume that P(n) is true. Then 2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4 and hence 2-2*7+2*7^2-...+2*(-7)^n +2*(-7)^(n+1)=(1-(-7)^(n+1))/4+2*(-7)^(n+1). =[(1-(-7)^(n+1))+8*(-7)^(n+1)]/4 =[1+(-7)^(n+1)*(-1+8)]/4 =[1+(-7)^(n+1)*(7)]/4 =[1-(-7)^(n+1)*(-7)]/4 =[1-(-7)^(n+2)]/4 which is exactly what we had to show: P(n+1) is true. 6: Let P(n) be "1*1! + 2*2! + ...+ n*n! = (n+1)! -1". The base case is easy. Assume P(n). Then 1*1! + 2*2! + ...+ n*n! + (n+1)*(n+1)! = (n+1)! -1 +(n+1)*(n+1)! by the inductive hypothesis = (n+1)! *[1+n+1] -1 = (n+2)! -1. This is precisely what P(n+1) says. 20: Let P(n)= " 3^n < n! for all n>6. The base case is n=7, the first number bigger than 6. There we have 3^7= 2187 and 7!=5040. So, ok. No assume P(n). Then 3^(n+1) = 3^n * 3 < n! * 3 (by inductive hypothesis) < n! * 4 < n! * 5 ... < n! *(n+1) = (n+1)!. That is what P(n+1) says. 32: Base case n=0 is true. 3 divides 0. (n+1)^3 +2*(n+1) = n^3 + 3*n^2 + 3*n + 1 + 2*n + 2 = n^3 + 2*n + 3*(n^2+n+1) By inductive hypothesis, n^3+2*n is a multiple of 3. Obviously, 3*(n^2+n+1) is also a multiple of 3. Hence their sum is a multiple of 3. TRhis sum equals (n+1)^3 +2*(n+1), hence P(n+1) holds. 49: The problem is that even though x and y are positive integers, the numbers x-1 and y-1 may not be. That means, that we cannot use the inductive hypothesis on x-1 and y-1. To see an explicit example how the proof fails, note first that the base case is ok: if you have 2 positive numbers x, y and their maximum is equal to 1, then they are both equal, x=y=1. If now we look at the next case, k=2, we could have x=1 and y=2. Their max is 2, and yet they are not equal. So with this choice of x and y the proof must fail. It does the moment that you try to use the "fact" that since x-1 and y-1 have max equal to 1 then they must be equal. This is an attempt of using the inductive hypothesis in the wrong way: since x=1, x-1 is NOT positive. So the base case (which only considers positive numbers) does not apply. And indeed, x-1=0 and y-1=1 are not equal. 7.5: 6: a) 10000 since adding A1 and A2 to A3 does not give anything that was not already in A3. b) 11100 since there is no overlap of the sets. c) If we just add them altogether, we get 11100. However, there are two elements in A1 intersection A2 that we counted twice, once for A1 and once for A2. So we should subtract them from 11100. Similarly we double counted the 2 elements common to A1 and A3, and the two elements common to A2 and A3. So the corrected count is 11100 - 6. Now however we made another mistake: there is one element that was in A1 and A2 and A3. This was counted 3 times in the sum 11100, and then taken out 3 times as one of the two elements in the corrected sum. So in the mumber 11100-6 it is not counted at all! Let's put it back in, then we get 11095. The general formula is written down on top of page 454. It comes from the double counting considerations we just went through. 12: There are 1000 integers not exceeding 1000. Of these, the squares of 1,2,...,31 are squares. Also, there are the 10 cubes 1,2^3,...,10^3. There are 3 numbers that are simultaneously squares and cubes: 1, 64 and 729. 1=1^2=1^3, 64=4^3=8^2, 729=27^2=9^3. Let A2 be the set of all squares, it has 31 elements. Let A3 be the set of all cubes, it has 10 elements. There are 3 in both, so the union of A2 and A3 has 31+10-3 = 38 elements. 20: 10000+10000+10000+10000+10000 -1000-1000-1000-1000-1000-1000-1000-1000-1000-1000 +100+100+100+100+100+100+100+100+100+100 -10-10-10-10-10 +1 (there are 5 sets, 10 2-fold intersections, 10 3-fold intersections, 5 4-fold intersections and 1 5-fold interesection) 28: The interesection of all pairs of events is empty. So the union of all n events has exactly as many elements as the sum of all the separate events. So the probability of the union of the n events is the sum of the n probabilities -- no fudge terms are required since there is no overcounting.