Answers to Test 2 Version 1

  1. There is a long rectangular table seating 1 at each end and 5 on each side in the President's dining hall.

  2. Recall that Pascal's Identity is the assertion that for integers
      n>= k > 0  

    C(n+1,k) = C(n,k-1) + C(n,k) .

    Give a combinatorial proof of this identity.

    Well you have seen the proofs. Your proof must adequately mention sets, partitions, and correspondences between sets.

  3. In this question we will have a recursively defined function H which will assign to every bit string w some other bit string H(w). Your ultimate goal is to simply tell me what the value of
    w = H(01001100011100001111000001111100000011111100000001111111).

    However I certainly do not want you to carry out the operation of H on the above string, rather I want you to formulate a verbal description of what H does to a string and prove, by induction, that this is the case.

    Here is the definition of H:

    H(lambda)= lambda where lambda is the empty string,

    for a string s, here are the values of H(s 0) and H(s 1):
    H(s 0) = H(s)

    H(s 1) = 1 H(s) 1

    If you didn't figure out what H is doing you haven't yet come to grips with recursion. Or more to the point you are not thinking of bit strings recursively. A bit string is a sequence of 0's and 1's (of course). The rules for H are telling you that if a bit string ends in a 0, then erase the 0 and compute H applied to the shorter string. If a string ends in a 1, figure out what H applied to the shorter string (with the 1 removed from the end) gives you, take that result and surround it by 1's. Hence, as stated on the test:
    H(101) = 1 H(10) 1 = 1 H(1) 1 = 1 11 1

    Thinking about this a bit more: H simply erases all the 0's in a bit string and doubles the number of 1's. Well this is our conjecture. Let P(n) denote the statement
    If s is a bit string with n bits, then H(s) is the bit string consisting of 2j 1's where j is the number of occurences of 1 in s

    We prove P(n) is true by induction. P(0) is true by inspection. Assume P(n) is true and let w be an arbitrary bit string of length n+1. There are two cases: First w could have the form s 0 and Second, w could have the form s 1. Clearly in both cases, s has length n, hence we know about H(s).

    Let j be the number of occurences of 1 in w. In the first case j is also the number of occurences of 1 in s. By definition, H(w) = H(s) and by inductive assumption, we know that H(s) consists of the string of 2j 1's. This is exactly what we want to prove about H(w).

    Now in the second case, we notice that s has exactly j-1 occurences of 1. Therefore H(s) is the string consisting of 2(j-1) 1's. Since H(w)= 1 H(s) 1, we see that H(w) consists of 2+ 2(j-1) = 2j 1's as required.