CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan,TA: Xiao Ke.
REVIEW5 SOLUTIONS

  1. Assume, there was   tex2html_wrap_inline294   units of the isotope at the hour  n. Then the amount of isotope left at the hour  n+1  will be   tex2html_wrap_inline300 . Hence we get the recurrence equation,   tex2html_wrap_inline302 and the initial condition will specify what   tex2html_wrap_inline304   was.

  2. Let   tex2html_wrap_inline306   be the number of bacteria after  n  hours, where   tex2html_wrap_inline310 . Then,   tex2html_wrap_inline312   since   tex2html_wrap_inline314   new bacteria are born at time  n,  these newly born ones should be added to those that already existed at time  (n-1). >From this total   tex2html_wrap_inline320   is subtracted because that many died at time  n. Initial conditions should specify   tex2html_wrap_inline324   and that   tex2html_wrap_inline326 .

  3. (a). Let   tex2html_wrap_inline328   be the number of permutations of a set with  n  elements. Clearly,   tex2html_wrap_inline332 . Then,   tex2html_wrap_inline334   is the required recurrence relation, since the first element can be chosen in  n  ways, and the remaining  n-1  elements can be arranged in   tex2html_wrap_inline340   ways.

    (b). Proof by iteration:   tex2html_wrap_inline332tex2html_wrap_inline344 ,   tex2html_wrap_inline346 ,   tex2html_wrap_inline348 ,   tex2html_wrap_inline350 . The product of the left hand side of the above equations is   tex2html_wrap_inline352 . The product of the right hand sides of the above equations is   tex2html_wrap_inline354 . Hence,

    displaymath266

    Cancelling,   tex2html_wrap_inline356   on either side of the above equation we get   tex2html_wrap_inline358 .

  4. Let   tex2html_wrap_inline328   be the number of ways of climbing  n  steps. Then, by the conditions of the problem,   tex2html_wrap_inline364 , since the person could have reached step  n  either by directly jumping to it from step  n-3,  or by jumping to it from step  n-2  or by stepping on to it from step  n-1. The initial conditions are,   tex2html_wrap_inline374   and   tex2html_wrap_inline376 .

  5. This problem was discussed in the solutions to review 1 problems. It should be clear that   tex2html_wrap_inline378   and   tex2html_wrap_inline380 .

  6. (a). Let   tex2html_wrap_inline382   be the number of different ways the driver can pay  n = 5m  cents using only nickels and dimes. Then   tex2html_wrap_inline386 ,  and   tex2html_wrap_inline388   since the last coin dropped by the driver could be either a nickel or a dime. This is the fibbonaci series.

    (b). The answer is   tex2html_wrap_inline382   for  m = 9.   tex2html_wrap_inline394   and   tex2html_wrap_inline396 .

  7. Let   tex2html_wrap_inline328   be the number of ways of getting stamps valued  n  cents. Initial conditions are,   tex2html_wrap_inline402   and   tex2html_wrap_inline404 . Then,   tex2html_wrap_inline406 ,  since stamps for  n  cents may be made up by adding a  10  cent stamp to stamps for  (n-10)  cents, a  6  cent stamp to stamps for  (n-6)  cents, or a  4  cent stamp to stamps for  (n-4)  cents.

  8. Let   tex2html_wrap_inline422   be the  nth Fibonacci number. For  n < 5  it is easy to see that   tex2html_wrap_inline428   for the initial conditions given in the problem. By repeated application of Fibonacci expansion, we have,   tex2html_wrap_inline422 = tex2html_wrap_inline432 = tex2html_wrap_inline434 = tex2html_wrap_inline436 . Thus, for   tex2html_wrap_inline438   also we have   tex2html_wrap_inline440 . Hence,   tex2html_wrap_inline440   for all   tex2html_wrap_inline438 .

    For   tex2html_wrap_inline446   we have   tex2html_wrap_inline448 . Clearly, for  n = 1,    tex2html_wrap_inline452 is divisible by 5.

  9. Assume,   tex2html_wrap_inline446   is divisible by 5. If we now prove that   tex2html_wrap_inline456   is divisible by 5, then we have the result.   tex2html_wrap_inline458   by the result proven above. But,   tex2html_wrap_inline460 ,  since   tex2html_wrap_inline462   is a Fibonacci number. Hence,   tex2html_wrap_inline464 . Clearly,   tex2html_wrap_inline466   is divisible by 5 and   tex2html_wrap_inline468   is divisible by 5 because of the induction hypothesis. Therefore,   tex2html_wrap_inline456   is divisible by 5. Hence, the result.

  10. We have,   tex2html_wrap_inline472tex2html_wrap_inline474 ,    tex2html_wrap_inline476 , and

    displaymath267

    displaymath268

    (a).
    tex2html_wrap_inline478 SRC="img60.gif" > ,   ALT="tex2html_wrap_inline480" SRC="img61.gif" > ,  tex2html_wrap_inline482   and   tex2html_wrap_inline484 . You can add up the result.

    (b).
    11,100.

    (c).
    tex2html_wrap_inline486 .

  11. There are  200  integers divisible by  5,   142  divisible by  7  (because   tex2html_wrap_inline496 )  and  28  which are divisible by both  5  and  7  (because   tex2html_wrap_inline504 ). The answer is  1,000  minus the number of integers which are divisible by  5  or  7, which is  1000 - (200 + 142 - 28).

  12. This is the same as   tex2html_wrap_inline514   (this is the number of integers that are divisible by 3) minus the number of integers that are divisible by both 3 and 7, namely   tex2html_wrap_inline516 .

  13. The largest integer  n  such that   tex2html_wrap_inline520   is  31. The largest integer  m  such that   tex2html_wrap_inline526   is  10. The number of integers less than 1000 which are both squares and cubes is just 1, since 1 is the only integer whose square is equal to its cube. Hence, the answer is  (31 + 10 - 1).

  14. Consider  fish  and  rat  as single tokens. The number of permutations containing  fish  is  (26 - 4 + 1)! = 23!, the number of permutations containing the token  rat  is similarly,  (26 - 3 + 1)! = 24!,  and the number of permumations containing both  fish  and  rat  is  (26 - 7 + 2)! = 21!.

    Hence the total number of permutations not containing  fish  or  rat  is, the total number of permutations of the 26 alphabets minus the number of permutations containing  fish  or  rat. This is  26! - (23! + 24! - 21!).

  15. Let   tex2html_wrap_inline560   for   tex2html_wrap_inline562   be the seven sets. There will be seven singleton terms,   tex2html_wrap_inline564 ,    tex2html_wrap_inline566 doubleton terms   tex2html_wrap_inline568 ,    tex2html_wrap_inline570   triples   tex2html_wrap_inline572 ,    tex2html_wrap_inline574   quadruples and   tex2html_wrap_inline576   quintuples. For  j > 5  all intersections of  j  sets will be empty. Hence, the answer is   tex2html_wrap_inline582 .

  16. This is   tex2html_wrap_inline584 minus the total number of bit strings that do contain four consecutive 1's. The number of bit strings that do contain 4 consecutive ones are

    displaymath269

    Hence, the answer is   tex2html_wrap_inline586 .

    Notice, this problem is in general hard to solve for  n-bit strings for arbitrary   tex2html_wrap_inline590 .

  17. If we throw a fair dice  8  times, the size of the sample space is   tex2html_wrap_inline594  . And that two sixes and two ones and one others, will appear in   tex2html_wrap_inline596  . Hence the probability of eight throws and get two sixs and two ones and one others is   tex2html_wrap_inline598 .

  18. When we draw balls out of the bag, with replacement, it's a Binomial distribution, we have

    displaymath270

    When we draw balls out of the bag, without replacement. It's Hypergeometric distribution (according to Theorem 3.6.3), we have

    displaymath271

  19. We draw cards from the pack without replcement. Again, Hypergeometric distribution:

    displaymath272

  20. This is also Hypergeometric distribution.
    (a).
    If we get more salmons than trouts, then the number of salmons is either   tex2html_wrap_inline600 . Hence we have

    displaymath273

    (b).
    If we get seven males

    displaymath274

  21. This uses Poisson distribution. An average of  3.2  telephone calls per hour to call X, in other word   tex2html_wrap_inline604 .

    eqnarray93

  22. It's also a Poisson distribution with   tex2html_wrap_inline606 .

    displaymath275

  23. In certain distance  s  feet, we have   tex2html_wrap_inline610 .

    displaymath276

    solve it get   tex2html_wrap_inline612  .
    It's no solution. So whatever the distance is we are never sure that we can find a sapling.

  24. Actually it's a Binomial distribution with  p=1/50 , but we also can use Poisson distribution to approximate it.

    displaymath277

    eqnarray135

    The claim that one out every fifty books brought out is a bestseller means   tex2html_wrap_inline616 .

    displaymath278

    eqnarray149

  25. It's Hypergeometric distribution. According to Theorem 3.6.3 (Larsen' book page 153), we have
    (a).
      tex2html_wrap_inline618 .

    displaymath279

    (b).
      tex2html_wrap_inline620  

    eqnarray183

  26. We can do it directly using Binomial distribution, certainly we can use Poisson distribution to solve it. we have   tex2html_wrap_inline622 .

    eqnarray208