CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
SOLUTIONS TO REVIEW PROBLEM SET 4

  1. We have   tex2html_wrap_inline333   ways to choose three numbers from ten numbers   tex2html_wrap_inline335  . And the biggest sum of these three numbers is  9+8+7=24 , and the smallest sum of these three numbers is  0+1+2=3 , thus we have  22  choice of the sum of the three numbers.
    According to the Pigeonhole principle, there are at least   tex2html_wrap_inline343   different ways to choose three numbers such that they have the same sum.

  2. We'll draw the transition table for the FSM.
    (a).
    The transition table for the FSM is following

    tabular13

    where   tex2html_wrap_inline381   is the starting state, and   tex2html_wrap_inline383   is the final state.

    (b).
    The transition table for the FSM is following

    tabular18

    where   tex2html_wrap_inline381   is the starting state, and   tex2html_wrap_inline447   is the final state.

    (c).
    The transition table for the FSM is following

    tabular23

    where   tex2html_wrap_inline381   is the starting state, and   tex2html_wrap_inline479   is the final state.

  3. In order to form a number greater than  4,000,000 , the most significant digit should be   tex2html_wrap_inline483  . When we choose  4  as the most significant digit, we have   tex2html_wrap_inline487   ways to choose the other digits. When we choose  5  as the most significant digit, we have   tex2html_wrap_inline491   ways to choose the other digits. Hence we have   tex2html_wrap_inline493   ways to form a number greater than  4,000,000.

  4. According to Course notes 1 page 23 (just before section 2.8.2), we have   tex2html_wrap_inline497   numbers between  0000  and  9999 , whose four digits form a nondecreasing sequence.

  5. We'll use following combinatorial arguments
    (a).
    The left handside says that we want to choose  r+k  balls from  n+k  balls. This can be done in   tex2html_wrap_inline507   ways.

    This may also be done by first splitting the  n+k  balls into two groups  A  and  B  each having  k  and  n  balls, respectively, and then picking  (k-i)  balls from group  A  and  (r+i)  balls from group  B  for   tex2html_wrap_inline527 . For each   tex2html_wrap_inline529   this can be done in   tex2html_wrap_inline531   ways. However, since   tex2html_wrap_inline533   we get

    displaymath277

    (b).
    A committee of  k  may be chosen from  n  people in   tex2html_wrap_inline539   ways and its chairman may be chosen in   tex2html_wrap_inline541   ways. Thue   tex2html_wrap_inline543   is the total number of ways one may choose a committee of  k  people out of  n,  with a chairman. For   tex2html_wrap_inline549   the total number of ways of doing this is therefore   tex2html_wrap_inline551 . This is the left hand side.

    The same committee selection with a chairman can also accomplished by first selecting a chairman, which can be done in   tex2html_wrap_inline553   ways, and then selecting an arbitrary subset of the remaining  (n-1)  people as members of the committee, which can be done in   tex2html_wrap_inline557   ways. Thus

    displaymath278

  6. Let  x  be any irrational number and let   tex2html_wrap_inline561   be  jx-N(jx)  where  N(jx)  is the integer closest to  jx  for   tex2html_wrap_inline569  . Each   tex2html_wrap_inline561   is an irrational number between  -1/2  and  1/2 . We will assume that  n  is any even number; the case where  n  is odd is messier.

    Consider the  n  open intervals   tex2html_wrap_inline583   and   tex2html_wrap_inline585   for tex2html_wrap275 :

    displaymath279

    displaymath280

    If for some   tex2html_wrap_inline569 ,   tex2html_wrap_inline589   or   tex2html_wrap_inline591   then we are done. If for none of the  j's,  tex2html_wrap_inline569   tex2html_wrap_inline561   is in   tex2html_wrap_inline599   or   tex2html_wrap_inline601   then all of the  n    tex2html_wrap_inline605 s  should be distributed among the remaining  (n-2)  intervals. Since there are  n-2  intervals and  n  numbers   tex2html_wrap_inline561 ,  by the Pigeonhole principle tells there should be an interval,   tex2html_wrap_inline583   for some  jtex2html_wrap_inline569   contain a   tex2html_wrap_inline621   and a   tex2html_wrap_inline623   with  r < s. Clearly then,   tex2html_wrap_inline627   and therefore   tex2html_wrap_inline629 .

  7. Let us define a random variable  X  as the score Linda gets. And we also define random variables   tex2html_wrap_inline633   as the scores Linda gets for each true/false and multiple choice questions, respectively. We have

    displaymath281

    displaymath282

    displaymath283

    displaymath284

    Assuming independence we get,

    displaymath285

  8. If we choose five books satisfying that no two books are adjacent, that means these five books has already divided the shelf into six parts   tex2html_wrap_inline635  , which each part satifying following constraints

    displaymath286

    And we also assume

    displaymath287

    Hence we have

    displaymath288

    And the number of solution to the above equation is   tex2html_wrap_inline637 . Thus there are   tex2html_wrap_inline639   ways to choose five books so that no two adjacent books are chosen.

  9. (a).
    If he has just one fruit a day, it will cost him seven days to eat the whole fruits. The number of ways for him to consume is   tex2html_wrap_inline641 .
    (b).
    If it will at most cost him seven days to consume the fruits, then we will have six divisor to divide the fruits. The number of ways to permutate the fruits and divisors is   tex2html_wrap_inline643 .
    (c).
    If all the fruits are identical, the number of ways to permutate the fruits and divisors is   tex2html_wrap_inline645 .

  10. The number of ways to get thirteen cards is   tex2html_wrap_inline647 .
    (a).
    We have only one ways to get all thirteen hearts, hence the probability is   tex2html_wrap_inline649 .
    (b).
    We have four ways to get thirteen cards of the same suit, hence the probability is   tex2html_wrap_inline651 .
    (c).
    We have   tex2html_wrap_inline653   ways to get seven spades and six clubs, hence the probability is   tex2html_wrap_inline655 .
    (d).
    We have   tex2html_wrap_inline657   ways to get seven cards of one suit and six cards of the other, hence the probability is   tex2html_wrap_inline659 .
    (e).
    We have   tex2html_wrap_inline661   ways to get six cards of one suit, six cards of a second suit, and one card of the other.
    (f).
    We have   tex2html_wrap_inline663   ways to get four cards of one suit and six cards of a second, two cards of the third, and one card of the fourth, hence the probability is   tex2html_wrap_inline665 .

  11. (a).
    Assume the number of bit string of length  n  not containing three consecutive zeros is  f(n) . And we can add a zero or a one in the end of a bit string of length  n  not containing three consecutive zeros to get a bit string of length of  n+1 . If the last three bit is  100 , we can't add a zero to it. We have

    displaymath289

    (b).
    The initial condition is

    displaymath290

    (c).
    We have

    displaymath291

    (d).
    Lets assume   tex2html_wrap_inline677  .

    displaymath292

    displaymath293

    displaymath294

    substituting the values for  f , we get

    displaymath295

    displaymath296

  12. Let  A  denote the event that all three chips drawn are white, and let   tex2html_wrap_inline683   denote the event that the  ith urn is sampled. And according to Bayes theorem, we have

    displaymath297

    and how to draw three chips without replacement is really an example of Hypergeometric distribution.

    displaymath298

    displaymath299

    Hence

    displaymath300

  13. First we shall declare there is a typing error in this problem, it should be

    displaymath301

    Since the chips are drawn with replacement and we are asked the probability of a white chip drawn for the first time, it's actually a Geometric distribution, with   tex2html_wrap_inline687 .

    eqnarray188

  14. Let  A  denote the event that only one color is left, and let  B  denote that only black chips are left, and let  W  denote that only white chips are left. We then have

    displaymath302

    In order to make only white chips left, we must draw at least  b  chips and at most  b+w  chips from the urn. It's a Hypergeometric distribution.

    eqnarray204

    Symmetrically, we have

    displaymath303

    Hence we have

    displaymath304