CS206 - SOLUTIONS TO REVIEW PROBLEM SET 1
Chitoor V. Srinivasan
Easy Problems

  1. In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, including the bride and groom, if
    1. the bride and groom should be next to each other?
    2. the bride must be in the picture ?
    3. the bride and groom must be in the picture ?
    4. only the bride or only the groom is in the picture?

    Answer:

    (a). The bride and groom may be arranged into a unit in  2!  ways. This unit may now be arranged with  4  people chosen from the remaining  8  in  5!  ways. Thus, the total number of ways of arranging  6  from  10  including the bride and groom is   tex2html_wrap_inline494 .

    (b). Choose the bride and  5  other people from among the remaining  9. This can be done in   tex2html_wrap_inline500   ways. The chosen six may be arranged in  6!  ways. Hence the answer is   tex2html_wrap_inline504 .

    (c). Choose the bride and the groom and  4  more people from the remaining  8. The selected  6  may be arranged in  6!  ways. Ans:   tex2html_wrap_inline514 .

    (d). Choose one of bride or groom and ask the other to leave. Choose  5  more from the remaining  8  and arrange the chosen six. Ans:   tex2html_wrap_inline520 .

  2. Suppose that at some future time every telephone in the world is assigned a number that contains a country code 1 to 3 digits long, i.e., of the form X, XX, or XXX, followed by a 10-digit telephone number of the form NXX-NXX-XXXX, where N is a non-zero digit. How many different telephone numbers would be available worldwide under this numbering scheme?

    Answer: The country code is a number between  0  and  999. This can be chosen in   tex2html_wrap_inline526   ways. The 10-digit telephone number may be chosen in   tex2html_wrap_inline528   ways, since the two  N's are required to be non-zero digits. Hence, the answer is   tex2html_wrap_inline532 .
  3. Suppose there are nine students in a discrete mathematics class at a small college.
    1. Show that the class must have at least five male or at least five female students.
    2. Show that the class must have at least three male students or at least seven female students.
    Answer:
    (a). Distributing 9 students among two sexes is the same as distributing Nine pigeons in Two holes.

    (b). If the number of students is at least three then the condition is already satisfied. If the number of males is less than three then the number of females has to be at least seven, since there are nine students in the calss.

  4. How many subsets with an odd number of elements does a set with 10 elements have?

    Answer: Every subset should have either an odd or even number of elements   tex2html_wrap_inline534 . The odd integers less than   tex2html_wrap_inline534 ,  are   tex2html_wrap_inline538 . The even integers less than   tex2html_wrap_inline534 ,  are   tex2html_wrap_inline542 . The number of subsets with odd and even number of elements are therefore, respectively,

    displaymath448

    displaymath449

    We have already seen that

    displaymath450

    Hence,

    displaymath451

    Since the total number of subsets is   tex2html_wrap_inline544   it follows that the number of subsets with odd number of elements is equal to the number of subsets with even number of elements, namely   tex2html_wrap_inline546 .

  5. The row of Pascal's triangle containing the binomial coefficients C(10, k),   tex2html_wrap_inline548 ,  is:

    displaymath452

    Use Pascal's identity to produce the row immediately following this row in Pascal's triangle.

    Answer:

    displaymath452

    displaymath454

  6. What is the probability that a positive integer not exceeding 100 selected at random is divisible by 3?

    Answer:
    There are 33 positive integers less than 100 which are divisible by 3. Hence the probability is   tex2html_wrap_inline550 .
  7. How many ways are there to select five unordered elements from a set with three elements when repetition is allowed?

    Answer:   tex2html_wrap_inline552 .
  8. How many solutions are there to the equation   tex2html_wrap436   where   tex2html_wrap_inline554 ,  and   tex2html_wrap_inline556   are nonnegative integers?
    Answer:   tex2html_wrap_inline558 .
  9. How many solutions are there to the inequality   tex2html_wrap_inline560   where tex2html_wrap_inline562 ,  and   tex2html_wrap_inline564   are nonnegative integers? Hint: Introduce an auxiliary variable   tex2html_wrap_inline556   and make tex2html_wrap437 .

    Answer:   tex2html_wrap_inline568 .
  10. In bridge, the 52 cards of a standard deck are delt to four players. How many different ways are there to deal bridge hands to four players?
    Answer:   tex2html_wrap_inline570 .
  11. Use a combinatorial arguments to prove the identity

    displaymath455

    Answer: The number of subsets of set containing  n  elements is the sum of number of subsets containing  i  elements for   tex2html_wrap_inline576   and there are   tex2html_wrap_inline578   ways of selecting a subsets with  i  elements.
  12. In how many ways can the letters   tex2html_wrap_inline582   be permuted such that no two a's are adjacent?

    Answer:  4!.
  13. Given thirty people, find the probability that among the twelve months there are six containing two birthday and six containing three.

    Answer: The size of the sample space is the same as number of ordered ways of selecting with repetition 30 months from the 12 in a year. Imagine the following experiment: Have the months arranged in an order, say

    displaymath456

    Each person is now thrown into one of the months. For each person there are 12 choices. Since there are 30 persons in all, the total number of choices is   tex2html_wrap_inline586 .

    The number of ways of choosing six pairs and six triplets of people from 30 is   tex2html_wrap_inline588 . Here, it is assumed that people with birthdays on the same month are indistinguishable from each other. One may check that   tex2html_wrap_inline588   is the same as

    displaymath457

    We have now chosen 12 groups of people consisting of 6 pairs and 6 triplets. Let   tex2html_wrap_inline592   and   tex2html_wrap_inline594   be the groups of pairs of people, and   tex2html_wrap_inline596   and   tex2html_wrap_inline598   be the groups of triplets. These 12 groups are distinct from each other and in each group there is no ordering of people inside the group. If months are and groups are arranged in order,

    tabular153

    then every permutation of the groups will produce a distinct matching of a month with a group. Every such matching will produce six months with 2 birthdays and six months with 3 birthdays. Hence the number of possible ways of getting six months with 2 birthdays and six with three birthdays is   tex2html_wrap_inline648   times the number of ways of producing the 12 groups, which is

    displaymath458

    Hence the probability is,

    displaymath459

  14. A group of  2N  boys and  2N  girls is divided into two equal subgroups. Find the probability  p  that each subgroup will have equal number of boys and girls.

    Answer: Each group should then have  N  boys and  N  girls. The number of ways of doing this is   tex2html_wrap_inline660 ,  i.e. choose  N  boys from the  2N  boys and  N  girls from the  2N  girls. The total number of ways diving  (2N + 2N)  boys and girls into two groups each containing  2N  individuals is   tex2html_wrap_inline674 . This is the size of the sample space. Hence, the probability is,

    displaymath460

  15. What is the probability that the bridge hands of North and South together contain exactly  k  aces, where   tex2html_wrap_inline678 ?

    Answer: The size of the sample space is   tex2html_wrap_inline680 . This is the same as the number of ways of distributing 26 cards to North and South. Let   tex2html_wrap_inline682   be the probability that North and South have  i  aces between them for   tex2html_wrap_inline686 .

    Then,   tex2html_wrap_inline688 ,  because 4 aces are taken out of the deck and given to East and West and the 26 cards of North and South are taken from the remaining 48 cards in the deck. Similarly,

    eqnarray185

    Notice,   tex2html_wrap_inline690   and   tex2html_wrap_inline692 . Can you give a combinatorial argument for this?

    Hard Problems

  16. Show that  (k!)!  is divisible by   tex2html_wrap_inline696   for any integer  k.

    Answer: We know that the number of ways of ordering  N  objects consisting of  M  kinds, each kind containing say  R  objects, is   tex2html_wrap_inline706 .

    By setting   tex2html_wrap_inline708   and  R = k  we get that   tex2html_wrap_inline712   is the number of ways of arranging  k!  objects consisting of  (k-1)!  kinds, each containing  k  objects. This should be an integer. Hence,  (k!)!  is divisible by   tex2html_wrap_inline696   for any  k.

  17. Among 10 billion numbers between  1  and  10, 000, 000, 000  how many contain the digit  1?
    Answer: This is the same as the total number of numbers minus the number of numbers that do not contain digit 1. The total number of numbers is 10 billion. The number of numbers that do not contain digit 1 is   tex2html_wrap_inline732 (because the number consisting of all zeros is excluded). Hence, the answer is   tex2html_wrap_inline734 .
  18. What is the number of  n-digit binary sequences that contain an even number of  0's?

    Answer: Take any  (n-1)-digit binary sequence, say   tex2html_wrap_inline742 . It can always be extened to an  n-digit binary sequence with even number of zeros as follows: If   tex2html_wrap_inline746   has an odd number of zeros then append a zero to it at the end to get an  n-digit binary sequence with an even number of zeros. If   tex2html_wrap_inline746   has en even number of zeros then append a 1 to it at the end. Thus, there are exactly   tex2html_wrap_inline752    n-digit binary sequences with an even number of zeros.
  19. Eleven scientists are working on a secret project. They wish to lock up the documents in a cabinet such that the cabinet can be opened if and only if six or more of the scientists are present.

    Answer: Every group of 5 scientists should not be able to open all the locks. Thus for each group of 5 scientists there should be at least one lock which they cannot open. Suppose,   tex2html_wrap_inline760   and   tex2html_wrap_inline762   are any two groups of five scientists. Let   tex2html_wrap_inline764 be the lock which   tex2html_wrap_inline760   could not open and   tex2html_wrap_inline768   be the lock which   tex2html_wrap_inline762   could not open. Then   tex2html_wrap_inline764   should be different from   tex2html_wrap_inline768 . If   tex2html_wrap_inline764   is the same as   tex2html_wrap_inline768   then no group of six scientists chosen from from   tex2html_wrap_inline780   will be able to open the cabinet. This will violate the requirement of the problem. Thus, distinct groups of 5-scientists should have distinct locks which they are not able to open. Hence, the number of needed locks is at least   tex2html_wrap_inline756   since there are this many distinct groups of 5 scientists.

    Let  A  be any one of the 11 scientists. For any group of 5-scientists chosen from the remaining 10 (excluding  A)  if  A  is added to the group then the six together should be able to open the cabiner. Since there are   tex2html_wrap_inline758   distinct groups of 5-scientists among the 10 (excluding  A)  it follows that  A  should have with him the keys to open every one of the locks which each group of 5 could not open. Thus,  A  should carry at least   tex2html_wrap_inline758   keys.

  20. In how many ways can three numbers be selected from the numbers   tex2html_wrap_inline800 , 300  such that their sum is divisible by 3? [ tex2html_wrap_inline804 ]

    Answer: When a number is divided by 3 the remainder can be  0,  1 or  2. Thus all numbers in the range  1  through  300  can be partitioned into three groups. Each one of these groups will contain exactly  100  numbers. Let   tex2html_wrap_inline818 ,   tex2html_wrap_inline820   and   tex2html_wrap_inline822   be these three groups.

    Three number whose sum is divisible by 3 may be chosen as follows: All three from   tex2html_wrap_inline824   in   tex2html_wrap_inline826   ways for   tex2html_wrap_inline828   or  2. Or, one number from each group; this can be done in   tex2html_wrap_inline832   ways. Thus we get the answer given above.

  21. How many divisors does  1, 400  have? (Hint:   tex2html_wrap_inline836 ).

    Answer: We have three 2's, two 5's and one 7, in all six integers. Any product of one or more inegers chosen from these six is a divisor of  1, 400. There are 4 ways of chosing zero or more  2's, 3 ways of chosing zero or more  5's and 2 ways of chosing zero or more  7's. If zero  2's, zero  5's and zero  7's are chosen then the divisor is 1,  otherwise the divisor is the product of the chosen numbers. Thus, the total number of divisors of  1, 400  is   tex2html_wrap_inline856 .
  22. In how many ways may seven flags be arranged on five masts if all the flags should be displayed but not all the masts need be used? (Hint: Use 4 indistinguishable dividers and 7 distinct balls analogy.)
    Answer: The 4 dividers will divide the 7 flags into 5 ordered groups in   tex2html_wrap_inline858   ways. The flags in any one group are assumed to be raised on the same mast. Notice, the order in which the flags appear in a mast from top to bottom matters here.
  23. Prove tex2html_wrap438 using Pascal's rule. What is its combinatorial significance?

    Answer: Pascal's rule says,   tex2html_wrap_inline860 . If you repeatedly apply this same rule to   tex2html_wrap_inline862   for   tex2html_wrap_inline864   to get the formula given above.

    It has the following combinatorial significance:  m  items can be chosen from  n+1  items, either by discarding the item, say   tex2html_wrap_inline870 ,  or by making sure, item   tex2html_wrap_inline870   is included. After including item   tex2html_wrap_inline870   one may chose the remaining  m-1  items from the left over  n-1  items by either discarding item, say   tex2html_wrap_inline880 ,  or by making sure, item   tex2html_wrap_inline880   is included. By repeating this argument successively over items   tex2html_wrap_inline884   one gets the formula given above.

  24. Prove tex2html_wrap439 .

    Answer:   tex2html_wrap_inline886 . Hence, if  x = 1  we get   tex2html_wrap_inline890 . The term by term differential of the binomial expansion of   tex2html_wrap_inline892   is

    displaymath461

    We get the result by setting  x  to  1  in the expansion on the right side of the above equation.

  25. Use a combinatorial argument to prove   tex2html_wrap_inline898   and   tex2html_wrap_inline900   are integers. In general, prove that   tex2html_wrap_inline902   is an integer.

    Answer: The first two parts are similar to problem 16 above. See solution of problem 16: we used  N  objects consisting of  M  kinds, each king having  R  elements.

    For   tex2html_wrap_inline898   set   tex2html_wrap_inline912   and  R = 2,  and for   tex2html_wrap_inline900   set   tex2html_wrap_inline918 ,  and  R = 3.

    For the last part set  M = R = n. Then we will have   tex2html_wrap_inline924   objects consisting of  n  kinds, each kind having  n  objects. The number of ways of arranging this is   tex2html_wrap_inline930 . Now notice, clearly, every arrangement,

    displaymath462

    will contain  n  kinds of objects in it. Think of these  n  kinds as  n  distinct colors, if you will. Let   tex2html_wrap_inline938   be the order of first appearence of colors in   tex2html_wrap_inline940 ,  i.e. color   tex2html_wrap_inline942   appears first, color   tex2html_wrap_inline944   is the second new color to appear in   tex2html_wrap_inline946 ,   tex2html_wrap_inline948   is the third new color, etc. Then, one could get  n!  rearrangments of   tex2html_wrap_inline940   by just permuting these  n  colors.

    Now define,   tex2html_wrap_inline940   is equivalent to   tex2html_wrap_inline958 ,  if   tex2html_wrap_inline958   may be obtained from   tex2html_wrap_inline940   by just permuting its colors. Then each equivalence class will be of size  n!  and the number of equivalence classes in the set of all permutations of the   tex2html_wrap_inline966   objects will be   tex2html_wrap_inline968 ,  by the division rule. Since the number of equivalence classes should always be an integer we get the result.

  26. Among  2n  objects  n  of them are identical. Find the number of ways to select  n  objects from these  2n  objects.

    Answer: One may choose  n  objects by choosing  i  of them from the set of  n  identical objects, and  (n-i)  of them from the remaining set of  n  distinct objects, where  i  may range from  0  through  n. The  i  identical objects may be chosen only in one way. Hence the solution is   tex2html_wrap_inline996 .
  27. A man is given  n  keys out of which exactly one opens a door. He tries them successively. This procedure may require  1,  2 tex2html_wrap_inline1000   trials. Show that each of these  n  outcomes has probability   tex2html_wrap_inline1004 .

    Answer: Clearly, the probability of chosing the right key the very first time is   tex2html_wrap_inline1004 . The probability of chosing the right key at the  kth  trial is the probability of not chosing the right key in the previous  k-1  trials and then chosing the right one at the  kth  trial. Thus, every success at the  kth trial will be preceded by a sequence of  k-1  incorrect keys. Since the total number of incorrect keys is  n-1,  the total number of such sequences which can lead to success at the  kth try is   tex2html_wrap_inline1022 . The sample space here is the number of  k-permutations of  n,  which is   tex2html_wrap_inline1028 . Hence, the probability of getting a success at the kth  try is

    displaymath463

  28. A closet contains  n  pairs of shoes, all mixed up. If  2r  shoes are chosen at random,  2r < 2n,  what is the probability that there will be (a) no complete pair, (b) exactly one complete pair, (c) exactly two complete pairs among them?

    Answer: There are   tex2html_wrap_inline1038   ways of chosing  2r  shoes from  2n  single shoes.

    (a). To assure no complete pair one should choose  r,  say from the let of  n  left shoes, and  r  from the complimentary set of  (n-r)  right shoes. The number of ways of doing this is   tex2html_wrap_inline1052 . Hence the probability is   tex2html_wrap_inline1054 .

    (b). For exactly one complete pair, through a similar argument we get the probability,   tex2html_wrap_inline1056 ,  since there are  n  ways of picking one complete pair and   tex2html_wrap_inline1060   ways of picking  2(r-1)  shows with no complete pairs.

  29. Show tex2html_wrap440 .

    Answer: Suppose there were  n  objects in two bags, say bags  A  and  B,  jointly containing  a+b  distinct objects,  A  containing  a  objects and  B  containing  b  objects. One may choose  n  objects from these two bags by choosing  i  from  A  and  (n-i)  from  B,  for   tex2html_wrap_inline576 . Hence,   tex2html_wrap_inline1092 .
  30. Show tex2html_wrap441 .
    Answer: We know that

    displaymath464

    Now set  y = 1-x  in the above equation. Then we get,

    tabular367

    Clearly, the above formula will sum to  1  only if the coefficient of   tex2html_wrap_inline1122   is zero for all   tex2html_wrap_inline1124 . The coefficient of   tex2html_wrap_inline1122   in the above expansion is the sum of the terms shown below:,

    tabular398

    which is the same as   tex2html_wrap_inline1144 . This solves the problem.