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.