Shai Simonson         CSC 201

    Discrete Math I for Computer Science

    Assignment 4

    Due:  Last day of class.

     0.    Book problems:  Section 6.1:   2, 4, 16, 28.    6.3:   8, 12, 14, 30, 34.  (Edition 7:  30 and 34 are 28 and 32)    7.2:   8, 24, 28.      8.5:  2, 4, 6.   
  1. Given ten points in the plane with no three collinear,
    1. How many different segments joining two points are there?
    2. How many ways are there to choose a directed path of length two through three distinct points?
    3. How many different triangles are there?
    4. How many ways are there to choose 4 segments?
    5. If you choose 4 different segments at random, what are the chances that some three form a triangle?

  2. Forty equally skilled teams play a tournament in which every team plays every other team exactly once, and there are no ties.
    1. How many different games were played?
    2. How many different possible outcomes for these games are there?
    3. How many ways are there for each team to win a different number of games?

  3. Let C(n, k) be the number of ways to choose k objects from a set of n. Prove by a combinatorial argument:
    1. C(n,0) + C(n, 1) + … + C(n, n) = 2n.
    2. C(n,m)C(m,k) = C(n,k)C(n-k, m-k).
    3. C(n, n-k) = C(n, k).
    4. C2(n,0) + C2(n, 1) + … + C2(n, n) = C(2n, n). (Hint: Use c, and consider that the 2n are n men and n woman).

  4. Prove the following combinatorial identities by formula.
    1. C(n+1, k+1) = C(n, k+1) + C(n, k).
    2. C(r, r) + C(r+1, r) + C(r+2, r) + … + C(n, r) = C(n+1, r+1).  Hint:  Use (a), and notice that C(r, r) + C(r+1, r) = C(r+2, r+1).  The series telescopes.
    3. Using the identity in 4b above, derive a formula for the sum (1)(2)(3) + (2)(3)(4) + … + (n-2)(n-1)(n).  Hint: Set r = 3.

  5. If you have 2n socks in a drawer, n white and n black, and you reach in to choose 2 socks at random,
    1. How many ways are there to choose?
    2. How many of these ways result in getting a pair of the same color?
    3. Write a simple closed form formula in terms of n for the chances of choosing a matching pair of socks from a drawer with n white and n black socks.

  6. A few short problems:
    1. How many ways are there to choose a president, vice president, secretary and treasurer from 9 people?
    2. How many ways can 13 identical balls be distributed into 3 distinct boxes?
    3. How many numbers greater than 3,000,000 can be formed from permutations of 1,2,2,4,6,6,6?
    4. How many nine-digit numbers with twice as many odd digits as even digits? (leading zeros are allowed, and zeros are considered even)
    5. How many passwords can be created in the form [A-Z][a-z]9[0,1]6? (That is, a capital letter followed by 9 lowercase letters followed by 6 bits).
    6. How many different 7-card Poker hands are there?
    7. How many 7-card poker hands are a flush (all one suit)?  (no need to subtract the straight-flushes).

  7. Let A and B be n-bit numbers, each representing a subset of n elements. For example, if the elements are {X, Y, Z}, then 000 is the empty set, 111 is the entire set, and 011, is the subset {Y, Z}.  What are the chances, given two randomly chosen n-bit numbers, that the first is a subset of the second?  Hints:  Count the total pairs of n-bit numbers, one from A and one from B.  Count how many of these pairs have the first set a subset of the second. You might get a sum involving combinations and powers of two but the answer can be reduced to something very simple using the binomial theorem.  Indeed, this very simple formula might suggest a much more clever but simpler way of solving this problem.

  8. How many ways are there to distribute eight balls into six distinct boxes with at least one ball in each box if:
    1. The balls are identical?
    2. The balls are distinct?  Hint:  Separate into disjoint cases and add.

  9.   How many ways are there to distribute eight balls into six distinct boxes with at most four balls combined  in the first two boxes if:
    1. The balls are identical?  Hint:  Separate into disjoint cases and add.
    2. The balls are distinct?  Hint:  Separate into disjoint cases and add.

  10.   Fibonacci in Pascal’s Triangle.

    11. Prove by induction that the nth Fibonacci number Fn equals C(n, 0) + C(n-1, 1) + C(n-2, 2) + … + C(ceiling(n/2), floor(n/2)).
    You should assume that F0 = F1 = 1.
     
  11. There’s a new screen saver that displays a random rectangular piece of an n by n checkerboard.
    1. How many rectangles are there in a checkerboard of size 1? 2? 3? 4?
    2. How many squares are there in a checkerboard of size 1? 2? 3? 4?
    3. Guess a general formula for the number of squares and rectangles. Put each in closed form in terms of n.
    4. Prove your formulas are true.
    5. What are the chances that the rectangle displayed is a square? Give a simplified closed form in terms of n.
    6. Although the number of squares and rectangles increase without bound as n increases, what happens to the ratio of squares to rectangles?

  12. A password is created with eight characters each of which is between the letters a and z inclusive.
    1. How many different passwords are possible?
    2. If no duplicate letters are allowed, then how many passwords are possible?
    3. In each case (a) and (b), if 2,000,000 random attempts are made by a hacker to guess the password, what are the chances that he cracks it?
    4. If it is known that the password is one of the 3,300,000 entries in a list of words and proper names, and again the hacker tries 2,000,000 random attempts to crack it. What’s the chance of his success?
    5. Assume one person out of 10,000 is infected with HIV, and there is a test in which 2.5% of all people test positive for the virus although they do not really have it. If you test negative on this test, then you definitely do not have HIV. What is the chance of having HIV, assuming you test positive for it?
  1. A round-robin tournament is one where each player plays each of the other players exactly once. Prove that if no person loses all his games, then there must be two players with the same number of wins. (Use pigeonhole principle). 

  2. Given any n + 1 integers from the set {1, 2, ... , 2n}, prove that there must be at least two where one is a multiple of the other. (Hint:  Write each number as 2m times an odd number, and consider the odd numbers as pigeons).

  3. Each of two disks has one billion bits around its perimeter, half of which are ones and half of which are zeros. Prove that no matter how the bits are arranged on each disk, the disks can be placed on top of each other, so that at least half a billion bits match up. (Hint: Count the total matches as you rotate the top disk around the bottom, and make a pigeonhole argument).

  4. How many different collections of four integers are there (duplicates allowed), where each integer is between 2 and 9, inclusive, and the sum equals 27? (Use Inclusion/Exclusion).

  5. Three computer tasks A, B, C each with 5 ordered parts: A1 through A5, B1 through B5, and C1 through C5, are being multi-tasked by my PC. Each task must execute its parts in order one through five.  Thus A1  B1 B2 C1 C2 C3 C4 B3 A2  etc. is an acceptable order.  Assume, that the choice of which task to work on next is chosen randomly, and that the next part of that task is then executed.  What is the probability that after all 15 parts are complete, five parts of at least one task were executed consecutively? (Use Inclusion/Exclusion).

  6. A password requires that you use a sequence of upper-case characters, lower-case characters and digits. A valid password must be at least 10 characters long, and it must contain at least one character from each of the three sets of characters. If you generate 10 random characters from the union of the three sets of characters, what is the probability that you will get a valid password? (Use Inclusion/Exclusion).

  7. What are the chances that a randomly dealt 13-card hand has at least one of every suit?  (Use Inclusion/Exclusion).

    back