CMSC 250 Fall 2004 -- Homework 10 Answer
Due Wed., Nov. 10 at the beginning of your discussion section.
You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.
  1. How many ways can the letters of the word JANPLANE be arranged in a row?
    Answer:

    $\displaystyle \frac{8!}{2!2!} = 10080$

    Explained: We look at the permutations of all 8 letters, but then we must remove the ones where the indistinguishable A's ($ 2!$) and the indistinguishable N's ($ 2!$) are the only differences.
  2. How many integers from 1 through 100000 is the sum of their digits equal to 9?
    Answer:

    $\displaystyle {r+n-1\choose r} = {9 + 5 - 1\choose 9}= 715$

    Explained: This is an example of the content of chapter 6.5. The r-Combinations with repetition allowed. We can look at the categories as the different digits of the number (there are 5 because since the value 100000 does not meet our criteria we are not concerned about 6 digit numbers). We can look at the x's to be placed in these categories as the 9 units that must be distributed among these 5 digits. For example $ \vert xx\vert \vert xx \vert xxxxx = 2025$ which is a value that meets our criteria and $ xxxx\vert x\vert\vert xx\vert xx = 41022$ which also meets our criteria.
  3. Leap years occur in years exactly divisible by four, except that years ending in 00 are leap years only if they are divisible by 400. How many leap years are in between 1563 and 2004 inclusive?
    Answer: In $ [1563,2004]$,
    # years that are divisible by 4 = This would be the same as looking at the integers between 391 and 501 (inclusively) because [391 times 5 = 1564] and [501 times 5 = 2004]

    $\displaystyle = 501-391+1 = 111 $


    # years that are divisible by 100 = This would be the same as looking at the integers between 16 and 20 (inclusively) because [16 times 100 = 1600] and [20 times 100 = 2000]

    $\displaystyle =20-16+1= 5$


    # years that are divisible by 400 = This would be the same as looking at the integers between 4 and 5 (inclusively) because [4 times 400 = 1600] and [5 times 400 = 2000]

    $\displaystyle 5-4+1= 2$



    Using the inclusion/exclusion rule:
    Therefore the number of leap years = $ 111 - 5 + 2 =108$.
  4. Let $ n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ where $ p_1,p_2,...,p_m$ are distinct prime numbers and $ k_1,k_2,...,k_m$ are positive integers. How many ways can $ n$ be written as a product of two positive integers that have no common factors?
    Answer: Since the two positive integers have no common factors, they have distinct prime factors in $ \{p_1,p_2,...,p_m\}$. So this problem relates to how many different ways to partition $ \{p_1,p_2,...,p_m\}$.
    1. assuming that order matters (i.e. $ 8\cdot15$ and $ 15\cdot8$ are regarded as different)?
      Answer: $ 2^{m}$
      Explained: For each of the m primes, we must decide to either put it in the first or in the second factor. By the multiplication rule this is $ 2^m$, Since you had 2 choices for the first, 2 choices for the second, 2 choices for the third, etc.
    2. assuming that order does not matter (i.e. $ 8\cdot15$ and $ 15\cdot8$ are regarded as the same)?
      Answer: $ 2^{m-1}$
      EXPLAINED: You again distribute the primes the way you did in part a, but you need to divide by 2 because as you were making the decisions on the individual primes you could have created the same two factors twice (in the opposite order) so each was counted twice. Dividing by 2 is the same as subtracting 1 from the exponent.
  5. A calculator has an $ n$-digit display and a decimal point that is located at the extreme right of the number displayed, at the extreme left, or between any pair of digits. The calculator can also display a minus sign at the extreme left of the number. How many distinct numbers can the calculator display? (Note that certain numbers are equal, such as 1.9, 1.90, and 01.900, and should, therefore, not be counted twice.) ANSWER:
    To do this problem you must partition it into smaller more manageable pieces. The first answer partitions into integers and non-integers. Integers are easy because we can always consider the situation that the decimal point is at the far right of the calculator. If the decimal point is not at the far right of the calculator and the value displayed is an integer, there must be 0's to the right of the decimal point (or it is not an integer) so those 0's are ones we can ignore because they are insignificant. They are the 0's the hint in the problem says we can ignore. Therefore we only count the ones where the decimal point is to the far right of the calculator display. Since the decimal point is already positioned, we only need to calculate how many different digits could be displayed and the sign of those digits. Since there are only 2 possible signs (positive or negative) the number of signs that need to be selected when creating a numeric value is 2. Since there are n places and 10 different values that can be in each place of the calculator, the number of possible digits in the display is $ 10^n$. Notice, this allows 0's in one or more places. If they are leading 0's they are insignificant and would be the same as a blank written before the number - thus we do not give the option of blanks or 0's since that would be double counting those values that are shorter (less digits) than n. Because both of the processes must be done, we use the multiplication rule to determine that the number of integers that can be displayed is $ 2 \times 10^n$. But this allowed the case that the calculator is filled with 0's to have both signs so we need to use the difference rule to take one of those away. Therefore the total number of integers that can be displayed is $ 2 \times 10^n -1$ The other (more difficult) partition is the non-integers. There are two different ways to look at this, but both involve the concept that the decimal point is not at the far right of the calculator display. The position of the decimal point can be in any one of the n positions that is not the far right. Notice that this is n positions beause it can be before the first position all of the way to before the last position (not after the last position. This means that one multiplier (when we apply the multiplication rule) must be the fact that the number of places where the decimal point can be placed is n. One way of looking at this part of the problem is to use the fact that if it is a non-integer, there must be at least one non-zero value to the right of the decimal point. Position that last non-zero value at the far right of the calculator display. This can be done for the same reason as the decimal point was positioned to the far right in the integer portion of the problem. If there are any digits to the right of this non-zero value, they would have to be 0's and therefore be insignificant and you don't want to count them as different values anyway. The number of ways to select this non-zero value is 9. This will then be one of the values we use when we apply the multiplication rule. The other places of the calculator could be any one of 10 different values because if they are 0's before the decimal point and before any significant non-zero digits, they are insignificant and could be replaced by spaces, but if they are after the decimal point or after a significant non-zero digit they make a difference in the value displayed. So the number of ways to fill in that is $ 10^{n-1}$. Using the multiplication rule on these three parts gives $ 2 \times 9 \times n \times (10^{n-1})$. Then using the addition rule because the subsets of integer and non-integer must form a partition of all values displayed gives us

    $\displaystyle 2 \times 10^n - 1 + 2 \times 9 \times n \times (10^{n-1})$





    OR




    This question can also be looked at as a major exercise in partitioning to smaller, more managable pieces. Each piece is not hard to count, and since they do form a partition we can just add them together. The numbers can best be counted by looking at strings of digits that do not have any significant preceeding or trailing 0's and then talk about deciding on the sign and positioning the decimal point. This will be done by first talking about the length of the string that starts and ends with a non-zero digit (it can have 0's between since they would be significant). The first partition is to divide the numbers that can be displayed into
    1. The values that do not have any significant preceeding or training 0's.
    2. The values that do have significant preceeding 0's (can't have any significant trailing 0's).
    3. The values that do have significant trailing 0's (can't have any significant preceeding 0's).
    We know these form a partition because they are completely defined on the existance/nonexistance of preceeding or trailing 0's. The first partition from above can be further partitioned into groups based on the length of that string (one that starts with a non-zero and ends with a non-zero.
    1. If the length of the string is 0, there is only one possible value. That value is 0. This is because the there are no non-zero digits, and the value of the sign and the position of the decimal point do not matter. There is 1 of these.
    2. If the length of the string is 1, there are 9 possible digits that could be in that string, 2 possible values for the sign (positive or negative) and 2 possible places where the decimal point could be (for example 9. or .9). This means that there are $ 9 \times 2 \times 2$ possible values represented where there are no significant preceeding or trailing 0's and the length of the string is 1. This means there are 36 of these.
    3. If the length of the string is 2 or greater. The number of values that can be represented where the string is x is $ 9^2 \times 10^{x-2} \times 2 \times (x+1)$. This is because the $ 9^2$ represents the selection of the 1st and last digits of the string (since they have to be non-zero. The $ 10^{x-2}$ represents the selection of each of the other characters in that string. The 2 represents the selection of the sign (positive or negative). The $ (x+1)$ represents the possible places for the decimal point since it can be immediately before the x character long string, immediately after the x character long string or between any two characters in the string. Summing all of the x length strings (to the max length of n) gives the number of values represented using strings of length between 2 and n.

      $\displaystyle \sum^n_{k=2} 9^2 \times 10^{x-2} \times 2 \times (k+1)$

    When these three items are added together they tell the number in the first of the partitions above. In other words, the number of values that can be represented when there are no significant preceeding or trailing 0's is:

    $\displaystyle 1 + 36 + \sum^n_{k=2} 9^2 \times 10^{x-2} \times 2 \times (k+1)$

    Now, onto the second and third partitions above. The method of calculating each of these is the same. We need to partition again based on the length of the string that starts with the first non-zero value and ends with the last non-zero value. Here we will just look at the values that have trailing 0's and then afterward multiply the answer by 2 to include those that have only preceeding 0's.
    1. When the lenth of the string is 0. It can't exists because the value 0 can not have significant trailing 0's (or signficant preceeding 0s').
    2. When the length of the string is 1. We need to decide on that one value (which there are 9 options for), and then decide on the sign, and then decide on the position of the decimal point to the right of that one non-zero value (not next to it). There are $ 9 \times 2 \times (n-1)$ ways this could be done.
    3. When the length of the string is more than 1. The number of values is represented by $ 9^2 \times 10^{x-2} \times 2 \times (n-x)$ because as the length of the string grows the number of places you can put the decimal point where it will not touch the string decreases. Looking at all strings whose length is 2 or greater we have:

      $\displaystyle \sum^n_{k=2} 9^2 \times 10^{k-2} \times 2 \times (n-k)$

    Counting all of the values that have training signififant zeros gives the count:

    $\displaystyle \left( 9 \times 2 \times (n-1)\right) + \left( \sum^n_{k=2} 9^2 \times 10^{k-2} \times 2 \times (n-k)\right)$

    Therefore we put togther the three original partitions and get:

    $\displaystyle \left( 1 + 36 + \sum^n_{k=2} 9^2 \times 10^{x-2} \times 2 \times ... ... + \left( \sum^n_{k=2} 9^2 \times 10^{k-2} \times 2 \times (n-k)\right) \right)$

    This reduces to:

    $\displaystyle = 1 + 36 - 36n -36 + \sum^n_{k=2} (9^2 \times 10^{k-2} \times 2 \times (k+1)) + 2 \times (9^2 \times 10^{k-2} \times 2 \times (n-k)$

    $\displaystyle = 1 + 36n + 9^2 \times 2 \times \sum^n_{k=2} \left( 10^{k-2} [(k+1) + (n-k) + (n-k)]\right)$

    $\displaystyle = 1 + 36n + 9^2 \times 2 \times \sum^n_{k=2} \left( 10^{k-2}[2n-k+1]\right)$

    which is equivalent to

    $\displaystyle 2 \times 10^n - 1 + 2 \times 9 \times n \times (10^{n-1})$

    You can prove these are equivalent by using the fact that

    $\displaystyle \sum^p_{j=0}ar^j = \frac{ar^{p+1}-a}{r-1}$

    and the fact that

    $\displaystyle \sum^p_{s=0}sx^s = \frac{px^{p+2} - (p+1)x^{p+1}+x}{(x-1)^2}$


Kin-Keung Ma 2004-11-12

Web Accessibility