Total points 50

   Bonus 5

Section 5.1 -- pp. 344 - 345

• 2 (1 pt)

  An office building contains 27 floors and has 37 offices on each floor. How any offices are there in the building?

  Product rule:    27 floors * 37 offices/floor = 27 * 37 offices = 999 offices

   

• 4 (1 pt)

  A particular brand of shirt comes in 12 colors, has a male version and a female version, and comes in three sizes for each sex. How many different types of this shirt are made?

  Product rule:    12 colors/version * 2 versions * 3 sizes = 72 types

   

• 10 (1 pt)

How many bit strings are there of length eight?

Product rule:    Each of 8 bits can be a 0 or 1: 2*2*2*2*2*2*2*2 = 2⁸ = 256

• 12 (2 pts)

  How many bit strings are there of length six or less?

  Product rule:   

  • 2⁶ = 64
  • 2⁵ = 32
  • 2⁴ = 16
  • 2³ = 8
  • 2² = 4
  • 2¹ = 2
  • 2⁰ = 1

  Sum rule:    64+32+16+8+4+2+1 = 127

   

• 16 (2 pts)

  How many strings are there of four lower-case letters that have the letter x in them?

  26⁴ strings of 4 characters, some include x

  25⁴ strings of 4 characters, all exclude x

  26⁴ - 25⁴ = 66,351 all include x

   

• 18 (6 pts)

  How many positive integers between 5 and 31

  1. are divisible by 3? Which integers are these?
  2. are divisible by 4? Which integers are these?
  3. are divisible by 3 and 4? Which integers are these?

1. The first integer between 5 and 31 divisible by 3 is 6. 

   9 integers: 6, 9, 12, 15, 18, 21, 24, 27, 30

2. The first integer between 5 and 31 divisible by 4 is 8. 

   6 integers: 8, 12, 16, 20, 24, 28

3. Intersection of a. and b.

   2 integers: 12, 24

• 26 (1 pt)

  How many license plates can be using either three digits followed by three letters or three letters followed by three digits?

  2*10³26³ = 35,152,000

   

• 52 (4 pts)

  Use a tree diagram to find the number of bit strings of length four with no three consecutive 0s.

  13 4-bit strings without 000.

  

  Another way:

  Note that there are 2⁴ = 16 permutations of 4-bit strings.

  With the substring 000, one bit remains, the 4-bit strings containing 000 are 0000, 1000, and 0001.

  3 strings with 000 so 16-3=13 strings without 000.

   

• Section 5.2 -- p. 353

  If N objects are placed into k boxes then there is at least one box containing at least éN/kù objects.

  #18 Hint:

  • 2 (1 pt)

    Show that if there are 30 students in a class, then at least two have last names that begin with the same letter.

    By pigeonhole principle, k=26, there are 30 people, at least one letter must occur twice or more as the first letter of a name.

    é30/26ù = 2

     

  • 4 (2 pts)

    A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them.

    1. How many balls must she select to be sure of having at least three balls the same color?
    2. How many balls must she select to be sure of having at least three blue balls?

     

    1. There are two colors.
       
       By Generalized Pigeonhole Principle, selecting N balls ensures there is one color of éN/2ù balls where we want éN/2ù ³ 3.
       
       Smallest integer is N=2*2+1 = 5.
        
    2. Possible to select all 10 red balls before selecting any blue. Must select 13 total.

     

  • 14 (4 pts)

     

    1. Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers that sum to 11.
    2. Is the conclusion in part (a) true if six integers are selected rather than seven?

     

    1. Consider the 10 integers in pairs that sum to 11:

    {1,10}, {2,9}, {3,8}, {4,7}, {5,6}

    Select any 7 of the numbers from the 5 sets. By the pigeonhole principle, we select one, complete pair.

    é7/5ù = 2

    Now select 5 numbers from the remaining 4 sets. By the pigeonhole principle, we select one, different, complete pair.

    é5/4ù = 2

    2. No. Assuming after selecting 6, which yields a pair summing to 11, we could only select 4 from 4 pairs remaining.

       é6/5ù = 2

       é4/4ù = 1

   

  • 18 (4 pts)

    Suppose that there are nine students in a discrete mathematics class at a small college.

    1. Show that the class must have at least five male students or at least five female students.
    2. Show that the class must have at least three male students or at least seven female students.

     

    1. Consider the N=9 students. By the Generalized Pigeonhole Principle, there is one gender of é9/2ù = 5 students.
        
    2. "If 9 students, then at least 3 are males or 7 are females."

       p ® q v r

       p is "9 students"

       q is "At least 3 males"

       r is "At least 7 females".

       Assume:

       p is true and q v r is false, that is: Ø(q v r) = Øq ^ Ør.

       Øq ^ Ør is "no more than 2 males" and "no more than 6 females"

       When no more than 2 males and no more than 6 females there are only 8 students.

       Contradicts assumption p, q v r cannot be false.

     

• Section 5.3 -- pp. 360 - 362
  • 2 (1 pt)

    How many different permutations are there of the set {a,b,c,d,e,f,g}?

    7!/(7-7)! = 7!/1 = 7! = 5040

     

  • 4 (3 pts)

    Let S = {1,2,3,4,5}

    1. List all 3-permutations of S.
    2. List all 3-combinations of S.

     

    1. 5!/(5-3)! = 120/2 = 60

       1 followed by 2,3 2,4 2,5 3,2 3,4 3,5 4,2 4,3 4,5 5,2 5,3 5,4

       2 followed by 1,3 1,4 1,5 3,1 3,4 3,5 4,1 4,3 4,5 5,1 5,3 5,4

       3 followed by 1,2 1,4 1,5 2,1 2,4 2,5 4,1 4,2 4,5 5,1 5,2 5,4

       4 followed by 1,2 1,3 1,5 2,1 2,3 2,5 3,1 3,2 3,5 5,1 5,2 5,3

       5 followed by 1,2 1,4 1,3 2,1 2,4 2,3 4,1 4,2 4,3 3,1 3,2 3,4

        

    2. 5!/3!(5-3)! = 120/6*2 = 10

       1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5

     

  • 6 (6 pts)

    Find the value of each of these quantities.

     

    1. C(5,1) = 5!/1!(5-1)! = 5!/4! = 5
        
    2. C(5,3) = 5!/3!(5-3)! = 5!/3!*2! = 120/12 = 10
        
    3. C(8,4) = 8!/4!(8-4)! = 8!/4!*4! = 8*7*6*5/4*3*2 = 7*2*5 = 70
        
    4. C(8,8) = 8!/8!(8-8)! = 8!/8! = 1
        
    5. C(8,0) = 8!/0!(8-0)! = 8!/8! = 1
        
    6. C(12,6) = 12!/6!(12-6)! = 12!/6!*6! = 12*11*10*9*8*7/6*5*4*3*2 = 924
        
  • 8 (1 pt)

    In how many different orders can five runners finish a race if there are no ties?

    P(5,5) = 5!/(5-5)! = 120

     

  • 10 (1 pt)

    There are six different candidates for governor of a state. In how many different orders can the names be printed on the ballot?

    P(6,6) = 6!(6-6)! = 6! = 720

     

  • 14 (1 pt)

    In how many different ways can a set of two positive integers less than 100 be chosen?

    C(99,2) = 99!/2!(99-2)! = 99*98/2 = 4851

     

  • 18 (4 pts)

    A coin is flipped four times where each flip comes up either heads or tails. How many possible outcomes

    1. are there in total?
    2. contain exactly three heads?
    3. contain at least three heads?
    4. contain the same number of heads and tails?

    Do this question flipping the coin 4 times, and draw a tree diagram from Section 5.1 to obtain the answers

    1. 2⁴
        
    2. C(4,3) = 4!/3!(4-3)! = 4
        
    3. C(4,3) + C(4,4) = 4!/3!(4-3)! + 4!/4!(4-4) = 4 + 1 = 5
        
    4. C(4,2) = 4!/2!(4-2)! = 24/4 = 6
        

     

  • 22 a. (1 pt)

    How many permutations of the letters ABCDEFGH contain the string ED?

    With ED substring have ABCEDFGH or 7 substrings.

    P(7,7) = 7!/(7-7) = 7! = 5040

     

  • 22 b. (1 pt)

    How many permutations of the letters ABCDEFGH contain the string CDE?

    With CDE substring have ABCDEFGH or 6 substrings.

    P(6,6) = 6!/(6-6) = 6! = 720

     

  • 26 a. (1 pt)  

    Thirteen people on a softball team show up for a game.

    How many ways are there to choose 10 players to take the field?

    C(13,10) = 13!/10!(13-10)! = 13*12*11/6 = 286

     

    How many ways are there to assign the ten positions by selecting players from the 13 people who show up?
     

  • 26 b. (1 pt)  

P(13,10) = 13!/(13-10)! = 1,037,836,800

 

 

• Section 5.4 -- pp. 369 - 370

• 2b (3 pts)    Bonus

  Find the expansion of (x+y)⁵ using Binomial Theorem

  

   

• 4 (2 pts)   Bonus