Assignment 5


Section 6.1:


6. Since the choice of routes from Boston to Detroit is independent of
the choice from Detroit to LA, the product rule says that we multiply
to get a total of 24 routes. 

22. Suppose we want to find the numbers divisible by n that are at
    least x and at most y. 
    Picture a clock with n hours, 0,...,n-1  Starting at x hours
    (0<x<y, all integers) and moving around the clock until y hours,
    count the mumber of times that zero hours are reached. This is
    equal to the number of inegers between x and y inclusively that
    are divisible by n. How many are there? Well, each time you go
    around the clock you find exactly one such number. The highest
    such number H you find is given by n times the round-down of
    y/n. The lowest number L you find is given by the round-up of
    x/n. (So for example, if x=1000 and y=9999 and n=9 then the first
    number we find is 9 times the round-up or ceiling of 1000/9, which is
    L=9*112=1008. On the other hand, the last such number we find is 9
    times the round-down or floor of 9999/9, which is H=9*1111=9999.)
    It is now easy to see that there are ((H-L)/n) + 1 such numbers.

    Armed with this formula, the number of integers in the interval
    [1000,9999] that are
    divisible by 1 is 9000,
    divisible by 9 is 1000,
    divisible by 2 is 4500,
    divisible by 3 is 3000,
    divisible by 5 is 1800,
    divisible by 7 is 1286,
    divisible by 5 and 7 (that is, by 35) is 257.

    Hence our answers are
    a) As noted, this is 1000. 
    b) And this is 4500. 
    c) There are 9 choices for the leading digit (1-9), 
       then 9 choices for the next digit (0-9 except for the digit
        already used),  
       then 8 choices for the third digit 
       and 7 for the finnal digit. 
       The number of choices at each step is independent of the other
       choices, so by the product rule we get a total of 9*9*8*7. 
    d) This is 9000 - 3000 = 6000. 
    e) There are 1800 divisible by 5, 1286 divisible by 7. The sum
       counts twice the numbers divisible by gcd(5,7)=35. So we
       get 1800+1286-257.  
    f) There are 1800 divisible by 5 and 1286 divisible by 7. If we
       subtract from the collection of all numbers those which are not
       divisible by 5, and then those not divisible by 7, we have twice
       removed those divisible by both 7 and 5. So we add them back in
       and the answer is 9000 - 1800 - 1286 + 257.
    g) The number divisible by 5 is 1800, as noted. From this we
       must subtract the number divisible by both 5 and 7, which is 257, as
       noted. Hence the answer is 1800   257 = 1543. 
    h) This is 257, as noted. 

32. a) There are 26 choices for each of 8 slots. By the product rule,
    there are 26^8 possible strings. 
    b) In this case there are 26 choices for the  1rst slot, 25 for
       the second, etc. for a total of 
       26*25*24*23*22*21*20*19. 
    c) This is the same as filling 7 slots with repetition, so we have
       a total of 26^7 strings. 
    d) This is the same as  filling 7 slots with no repetition
       and no X, so we have a total of 25*24*23*22*21*20*19. 
    e) This is the same as  filling 6 slots with repetition, so we
       have a total of 26^6 strings. 
    f) This is the same as  filling 6 slots
       with repetition, so we have a total of 26^6 strings. 
    g) This is the same as  filling 4 slots with repetition, so we
       have a total  of 26^4 strings. 
    h) There are 26^6 strings the start with 'BO', and the same number
       that end with 'BO'. Also, there are 26^4 that start and end with
       'BO'. By the principle of inclusion/exclusion, the total is 26^6 +
       26^6 - 26^4. 

40. The total number of subsets of a set with 100 elements is
    2^100. The number of subsets with no elements is 100 choose 0,
    equal to one. And there are 100 choose 1 equal to 100 subsets of
    size 1. So the answer is 2^100-1-100.



46. a) There are 6 choices for the position of the bride. From the
       remaining positions, we have 9 choices for the  1rst, 8 for the
       second etc. This gives 6*9*8*7*6*5 = 90720. 
    b) There are 6 choices for the position of the bride, then 5 for
       the position of the groom. Choosing the remaining people as in
       part (a), we get a total of 6*5*8*7*6*5 = 50400. 
    c) We use the principle of inclusion-exclusion. From part (a) the
       number with the bride in the picture is 90720, and this is the
       same as the number with the groom in the picture. We add these,
       then subtract twice the number in which both appear. This gives 80640. 

50. We  first count the number of strings with 5 consecutive
    0's. Consider the position of the first zero in this string. If
    this is in position 1, then there are 2^5 ways of filling up the
    last 5 spots. If it is in position 2, then in position 1 there is
    no zero, hence there are only 2^4 ways of filling up the last 4
    positions. If the 0-string starts in position 3, then in position
    2 was no 0, so there are 2^4 ways again to fill up positions 1,
    8,9,10. Similarly there are 2^4 ways of having the first zero show
    up in positions 4, 5 or 6. We conclude that there are
    2^5+2^4+2^4+2^4+2^4 ways of having a string of five (or more)
    zeros. 

    By symmetry of the question, there are just as many strings with 5
    (or more) consecutive 1's. 

    There are 2 strings that have both, (1,1,1,1,1,0,0,0,0,0) and
    (0,0,0,0,0,1,1,1,1,1). 

    Hence the answer is 2*(2^5+5*2^4)-2 by inclusion/exclusion.  



73. We can make a diagonal by choosing two of the vertices and
    connecting them as long as we exclude adjacent vertices. There are
    n edges, so n times choosing two vertices will not give a
    diagonal. Since there are n choose 2 ways of picking a pair of
    vertices, there are n choose 2 minus n diagonals. 

    Alternatively, from each vertex can be drawn n-3 diagonals. So
    there are n(n-3)/2 diagonals, since each diagonal is counted
    twice.



7.4::

6:  There (50 choose 6) ways of filling a lottery ticket, and just one
    of them wins. The one winning ticket has a rpobabilty of 1/(50
    choose 6). The expected winning is: 10 million/ (50 choose 6).This
    is about 0.63. This means that if you play this game a large
    number of times (like a few trillion times or more) then
    statistically you have lost 37 cents from every dollar per
    game. The lottery company will want this number 62 cents of a
    dollar to be close to 1 but not larger than 1. This way people
    think they have a fair shot and the company still makes money. Of
    course they are NOT GUARANTEED to make money, because it is
    conceivable that you go and hit the jackpot 57 times in a row. It
    just is not LIKELY that you do.

8:  There are 3^6 possible outcomes of rolling 3 dice. The outcomes are
    (1,1,1), (1,1,2),..., (6,6,6). Each has probability 1/216. The
    random variable we want to look at is the sum of the rolls.
    We need to evaluate a sum of the type: 
        6          6         6
      (sum)      (sum)     (sum)  [ (a+b+c)/216 ]
       a=1        b=1       c=1

       which comes out to be 21/2. 

12: To have a 6 in a roll the chance is 1/6, so the chance not to have
    a 6 is 5/6. 
    a) If we roll the first 6 with the n-th roll, there were n-1
    not-sixes, and one six. The probability for that is (5/6)^(n-1) *
    (1/6). 
    b) We need to make a sum of the form

         infinity
          (sum)     n* (5/6)^(n-1) * (1/6)
           n=1

      and we recognize this as an example of a geometric distribution
      with parameter p=1/6. The book, or class notes, tell us that the
      expected value is 1/p = 6. 

16: We recall that "X and Y are independent" means that for all
    choices of r and s there is an equality 
    p(X=r) * p(Y=s) = p(X=r and Y=s).
    For example, we could take r=1 and s=2. r=1 means to have one
    head, which happens in 2 of 4 cases: (HT), (TH). 
    s=2 means to have 2 tails. So p(X=1)*p(Y=2) = (1/2) *(1/4).
    OTOH, "X=1 and Y=2" cannot happen, because you can't have 2 T and
    a H in 2 coins. So p(X=1 nd Y=2)=0. 0 is not (1/2)*(1/4), so X and
    Y are not independent.