Shai Simonson         CS 201

    Discrete Math I for Computer Science

    Assignment 4

    Due:  Before final

     0.    Book problems:  5.1 -  2, 4, 16, 26.    5.3 -  8, 12, 14, 28, 32.    6.2 -  8, 24, 28.      7.6 -  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 segments at random, what is the chance 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 different 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).
  4. Prove the following combinatorial identities by formulae or mathematical induction
    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).
    3. Using the identity in 4b above, derive a formula for the sum (1)(2)(3) + (2)(3)(4) + … + (n-2)(n-1)(n).
  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 chance 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)
    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).
  7. Poker:
    1. How many different 5-card Poker hands are there?
    2. How many of these are 1 pair?
    3. How many of these are a flush (all one suit)?
    4. How many are a full house (3 of a kind and a pair)?
  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?
  9.   How many ways are there to distribute eight balls into six distinct boxes with at most four balls in the first two boxes if:
    1. The balls are identical?
    2. The balls are distinct?
  10.   Fibonacci in Pascal’s Triangle.

    11. Prove by induction that the nth Fibonacci number Fnequals C(n, 0) + C(n-1, 1) + C(n-2, 2) + … + C( én/2ù , ë 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 either by induction or using a combinatorial argument.
    5. What’s the chance 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. How many different passwords are possible?
    1. If no duplicate letters are allowed, then how many passwords are possible?
    2. In each case, if 2,000,000 random attempts are made by a hacker to guess the password, what’s the chance that he cracks it?
    3. 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?
    4. 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 mustbe two players with the same number of wins.
  1. Each of two disks has one megabyte of bits around its perimeter, half of which are ones and half of which are zeros. Prove that no matter how the bits are arranged, they can be placed on top of each other, so that half a megabyte of bits match up. (Hint: Count how many total matches as you rotate the top disk around the bottom, and make a pigeonhole argument).
  1. How many different collections of six integers are there (duplicates allowed), where each integer is between 0 and 8, and the sum equals 20? (Use  Inclusion/Exclusion).
  1.  Three computer tasks each with 5 ordered parts, are being multitasked by my PC. 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 one task were executed consecutively? (Use Inclusion/Exclusion).
  1. 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? Same question when a valid password must contain at least two characters from each of the three sets of characters.
    back
     

    shai@stonehill.edu

    http://www.stonehill.edu/compsci/shai.htm