CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 1 SOLUTIONS

  1. First choose numbers   tex2html_wrap_inline97 m from the m numbers and then choose (n-2) numbers from the remaining set of (m-2) numbers There are C(m-2,n-2) ways of doing this. We've now chosen a set of n numbers that includes both   tex2html_wrap_inline99   and   tex2html_wrap_inline101 . These n numbers may now be ordered in n! ways. Hence the answer is C(m-2,n-2) * n!

  2. C(p,k) = tex2html_wrap85 Since C(p,k) is an integer,  k!(p-k)!  divides  p! = p (p-1)!. Since tex2html_wrap_inline107 and  p  is a prime, there is no factor of  p  in the denominator. Therefore,  k!(p-k)!  divides  (p-1)! implying that tex2html_wrap_inline117 is an integer. Hence, C(p,k) = p tex2html_wrap_inline119 an integer, and  p  divides C(p,k)

  3. A. Suppose we want to choose from n people, a committee size r and a sub-committee of size k. We can do this two different ways. We can first choose a committee size r and then choose k of the committee to form the sub-committee. We can do this in C(n,r) * C(r,k) ways. Alternatively, we could first choose the k members of the sub-committee and then choose the remaining r-k members of the committee from the remaining n-k people. This can be done in C(n,k) * C(n-k,r-k) ways. Thus, C(n,r) * C(r,k) = C(n,k) * C(n-k,r-k)

    B. tex2html_wrap_inline123
    tex2html_wrap_inline125

  4. A. Suppose we want to choose 2 people from a set of n men and n women. We could combine the men and women into one set and select 2 from this set of 2n people. This can be done in C(2n,2) ways. Alternatively we could either select 2 men, 2 women, or one of each. Respectively, this can be done in C(n,2), C(n,2) and   tex2html_wrap_inline127   ways. Thus, C(2n,2) = 2 * C(n,2) +   tex2html_wrap_inline127

    B. tex2html_wrap_inline131
    tex2html_wrap_inline133

  5. Base case: tex2html_wrap_inline135

    Induction step: Assume the theorem is true for k. Show that it holds for k+1.

    displaymath87

    In order to get the exponents in the two summations the same, substitute i+1 = j in the right summation (this will also change the bounds of the summation). This yields

    displaymath88

    The indexes don't go over the same bounds. Thus I'll move the first summation's first term out of the summation and I'll move the second summation's last term out of the summation. For consistency I'll use index variable j in both summations. This yields

    displaymath89

    displaymath90

    Applying Pascal's rule we get

    displaymath91

  6. There are 99,999,999 different wages from .01 to 999,999.99. By the pigeonhole principle, two people earned the same amount.

  7. 28, by the pigeonhole principle.

  8. Divide the set {1,2,3,...,2n} into n pairs, (1 2), (3 4), (5 6), ... (2n-1 2n). We are picking n+1 numbers so by the pigeonhole principle, at least one of the pairs would have both of its numbers picked. The GCD (greatest common divisor) of any two consecutive numbers is 1.

  9. Divide the square four quarters (use a vertical and a horizontal dividing line). Pick 5 points. By the pigeonhole principle, at least two must come from the same quarter. These two points can be at most tex2html_wrap_inline137 apart.
  10. You need to pick 20 coins from 5 types. Thus, the problem reduces to finding the number of ways in which 20 could be partitioned into 5 groups, which is  C(24,4).

  11. We want a number from 1 through 999,999. If we pad small numbers with leading 0s, then all numbers will have 6 digits. (e.g. We will select the number 000094 instead of 94). The 9 could be in any of 6 places. The remaining 5 digits must total 4. This is equivalent to partitioning 4 balls into 5 groups (the digit corresponding to a group is the sum of the number of balls in the group). The number of ways is thus, 6 C(4+5-1,5-1) = 6 C(8,4) = 420.

  12. First choose   tex2html_wrap_inline141   objects of type 1,   tex2html_wrap_inline143   objects of type 2,   tex2html_wrap_inline145     tex2html_wrap_inline147   objects of type r. This can be done in one way. Now all that remains is to choose   tex2html_wrap_inline149 objects from r types. The number of ways follows from the partition rule.

  13. First, we seat the girls, which can be done in 8! ways. There are 9 places now in which to seat the 6 boys, so we want a 6-permutation from 9 things which can be done in 9!/3! ways. Thus, there are 8! * 9! / 3! ways. This solutions assumes that each person is distinct. if you consider each girl as being the same and likewise each boy being the same, then seating the girls is done in one way. Then we would need to choose 6 of the 9 possible seats for the boys. This can be done in C(9,6) ways.