CMSC 250 Fall 2004 -- Homework 11 Answer

Due Wed., Nov. 17 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. Solve each of the following giving the formula used, explanation in English of why that formula was used and the answer (only needs to be taken to a fomula that involves exponents, factorial, addition, subtraction, multiplication and/or division).
   1. A farmer with 7 cows likes to milk them in a different order each morning. How many days can he do this before he has to repeat an order already used?
      Answer: The number of ways to order the cows in a single line is calculated as a permutation of the seven cows.
      # of different orders = $7!$
      Therefore this is the number of days he can go without repeating the same pattern. If he goes 1 more day he will need to repeat a pattern already used.
   2. A man has 5 sport coats, 4 pair of slacks, 6 shirts and 1 tie. How many different outfits can he make if an outfit must at least consist of a pants and shirt? (He does not care about matching, and notice coat and tie are optional.)
      Answer: We can partition this problem into four smaller problems: No coat and No Tie, No coat and Yes tie, Yes coat and No Tie, and Yes Coat and Yes Tie.
      The No Coat and No Tie is just a matter of selecting a pants and shirt: $4* 6 = 24$
      The No Coat and Yes Tie is a matter of selecting the pants and shirt and then since there is only 1 tie there are really no choices there: $4*6*1 = 24$
      The Yes Coat and No Tie is a matter of selecting the pants, shirt and coat: $5 * 4 * 6 = 120$
      The Yes Coat and Yes Tie is a matter of selecting the pants, shirt and coat and including the one tie: $5 * 4 * 6 * 1 = 120$
      Since these subproblems form a partition, we can add them to get $288$.
      OR
      Since cost and tie are optional, we model this by adding 1 (empty coat/tie) to the quantities of coats and tie.
      # different outfits = $(5+1)\times4\times6\times(1+1) = 288$
   3. A dinner special for 4 at a Chinese restaurant allows one shrimp dish (from 3), one beef dish (from 5), one chicken dish (from 4) and one pork dish (from 4). Each individual diner can also choose either soup or an egg roll. Assuming a group of 4 diners has come in and agreed on the items in the special, how many different orders could be sent from the kitchen?
      Answer: There are two different possible interpretations for this problem. You could interpret the soup/eggroll option as the idea that each diner must select one of these, but a valid interpretation would also give the diner the option of selecting to have neither soup nor eggroll.
      # of different entre combinations = $3\times5\times4\times4 = 240$
      # of soup/eggroll chosen is range from 0 to 4. That are 5 possibilities.
      # of different orders = $3\times5\times4\times4\times5 = 1200$
      OR
      # of different entre combinations = $3\times5\times4\times4 = 240$
      # of soup/eggroll/none chosen is $\frac{4 + (3-1))!}{4!(3-1)!}=15$ # of different orders = $3\times5\times4\times4\times5 = 3600$
   4. You are the judge in a child's costume contest. You want to make sure everyone gets a prize. There are 21 contestants. You develop 7 categories and give out first, second and third place prizes in each category. You can assume that each child gets one and only one prize.
      1. Assuming every prize is different, how many different ways can the 21 prizes be given to the 21 children?
         Answer: $21!$ Because this would be the same as assuming the prizes are in a specific order and you must line up the children so that the first child receives the prize that is first in the prize order.
      2. Assume you take pictures of the winners in each category (this would be 7 pictures with 3 people in each picture). You do not indicate who won first second or third place - it is just a picture of which of the 7 categories the children are in, how many different ways can they be placed into those 7 categories?
         Answer: There are $21!$ different ways to line the children up in a single line. They are then divided so that the first 3 are in the first photo, the second 3 in the second photo, etc. In each photo the place awarded (1st, 2nd and 3rd) are indistinguishable. Therefore answer = $21!/(3!)^7$
         You could also look at this as positioning the children by selecting who will be in each of the pictures
         
         $${21 \choose 3}{18 \choose 3}{25 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}$$
         
         
         This gives the same answer.
      3. Assuming the prizes handed out for first place are all the same, the prizes for second place are the same and the prizes for third place are all the same, how many different ways can children leave with their prizes?
         Answer: There are 21! ways to organize the children into a straight line. These could then be divided so that the 1st 7 receive 1st place prizes, the 2nd 7 receive 2nd place prizes and the last 7 receive 3rd place prizes. Since the prizes for one place are indistinguishable from each other, we need to divide by the sizes of each of those indistinguishable subsets. $21!/(7!)^3$
   5. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants and broccoli croissants. Assume the shop has as many of each of these type as you need to answer the questions below. How many ways are there to choose
      1. a dozen croissants?
         Answer: choose 12 elements from a set of 6 elements with repetition. Answer = ${12+6-1\choose 12} = \frac{(12+(6-1))!}{12!(6-1)!}$
      2. three dozen croissants?
         Answer: choose 36 elements from a set of 6 elements with repetition. Answer = ${36+6-1\choose36} = \frac{36+(6-1))!}{36!(6-1)!}$
      3. two dozen crossants with at least two of each kind?
         Answer: We can picture this that the 12 (the two of each kind) are already in the bag. Then we just need to calculate how many ways to select the other 12.
         
         $$\frac{(12+(6-1))!}{12!(6-1)!} = 6188$$
         
         

      4. two dozen croissants with no more than two broccoli croissants?
         Answer: This can be done by partitioning so that you have either 0 broccoli croissants, 1 broccoli croissant or 2 broccoli croissants.
         NO broccoli croissants:
         
         
         $$\frac{(24+(5-1))!}{24!(5-1)!} = 20475$$
         
         
         1 broccoli croissant:
         
         
         $$\frac{(23+(5-1))!}{23!(5-1)!} = 17550$$
         
         
         2 broccoli croissants:
         
         
         $$\frac{(22+(5-1))!}{22!(5-1)!} = 14950$$
         
         
         To get the answer we sum them together because they are partitions.
      5. two dozen croissants with at least one plain, at least two cherry, at least three chocolate, at least one almond and at least two apple, and no more than one broccoli croissants?
         Answer: Firstly, we reserve $(1+2+3+1+2)=9$ croissants for those ``at least'' constraints. Then we have 15 croissants left. We reserve the 9 croissants (considering the ``at least'' ones) to be already in the bag. Then we partition the distribution of the remaining ones into 0 broccoli croissants or 1 broccoli croissant.
         0 broccoli croissants:
         
         
         $$\frac{(15+(5-1))!}{15!(5-1)!} = 3876$$
         
         
         1 brocoli croissant:
         
         
         $$\frac{(14+(5-1))!}{14!(5-1)!} = 3060$$
         
         
         Adding them together we get 6936.
   6. The following questions are all about a standard deck of 52 playing cards.
      ANSWER: This question had multiple interpretations based on the issue of how much people read into it about playing the game. Are the people sitting in a line or circle, does where they are sitting in relation to each other matter, etc.? Because of this, we are not going to grade this one exactly - only if they had some consistant logical interpretation.
      
      1. Assuming you are planning to deal the entire deck of 52 cards to 4 players so that each player gets 13 cards randomly, how many ways could these cards be distributed to 4 distinguishable players? ANSWER:
         The number of ways to make 4 different hands: $52!/(13!)^4$ because this is the same as the ways to select which cards people have:
         
         $${52 \choose 13}{39 \choose 13}{26 \choose 13}{13 \choose 13}$$
         
         
         An alternative interpretation would be considering the position of the players for the game. If you are considering the position of the players would would also need to consider the number of ways to distribute those hands to 4 players: $4!$
         Since both of these actions must be done, we apply the multiplication rule.
         Since the position of the players were not mentioned in the problem, this portion would be optional since the first part would count all of the ways of distributing the hands to all of the players.
      2. If you deal all of the cards randomly to 4 players so that each player gets 13 cards, what is the probability that each and every player will have 13 cards that are all of the same suit?
         Answer: Among the ways of deal there are only $4!$ ways to make each and every player have 13 cards that are all of the same suit. Therefore answer = $\frac{4!}{52!/(13!)^4}$
         (the denominator would be your answer to i)
      3. If you deal all of the cards randomly to 4 players so that each player gets 13 cards, what is the probability that each and every player has exactly one ace?
         Answer: Take 4 aces out of the deck. There are $48!/(12!)^4$ ways to deal the rest of the cards randomly to 4 players so that each player gets 12 cards. And there are $4!$ ways to deal 4 aces to them. Therefore answer = $\frac{4!48!/(12!)^4}{52!/(13!)^4}$ (again, your denominator should be your answer to part i)
   7. There are 10 questions on a discrete math exam. How many ways are there to assign scores to the problems if the sum of the scores is 100 and each question is worth at least five points?
      Answer: Reserve 5 points to each of the 10 questions. The rest of 50 points can be assigned to the 10 questions arbitrary. Therefore answer = $50 + 10-1 \choose 50 = \frac{(50+(10-1))!}{50!(10-1)!}$
2. Let $m$ be any nonnegative integer. Use mathematical induction and Pascal's formula to prove that for all integers $n\geq 0$,
   
   $${m\choose 0}+{m+1\choose 1}+\cdots+{m+n\choose n} = {m+n+1 \choose n}.$$
   
   
   
   Answer: Base case ($n=0$):
   $LHS = {m+0\choose 0} = 1$, $RHS = {m+0+1\choose 0 } = 1$. Since $LHS=RHS$ the claim holds for $n=0$.
   Induction hypothesis ($n=k$):
   
   $${m\choose 0}+{m+1\choose 1}+\cdots+{m+k\choose k} = {m+k+1 \choose k}.$$
   
   
   Induction step ($n=k+1$):
   show:
   
   $${m\choose 0}+{m+1\choose 1}+\cdots+{m+k+1\choose k+1} = {m+k+2 \choose k+1}.$$
   
   
   Proof:
   ${m\choose 0}+{m+1\choose 1}+\cdots+{m+k+1\choose k+1}$
   $={m\choose 0}+{m+1\choose 1}+\cdots+{m+k\choose k}+{m+k+1\choose k+1}$ by expansion of the series
   $={m+k+1 \choose k}+{m+k+1\choose k+1}$ by IH
   $={m+k+2 \choose k+1}$ by Pascal's formula
3. Express each of the sums in closed form (without using a summation symbol and without using an ellipsis $\cdots$).
   1. $$\sum_{i=0}^m {m\choose i} 4^i$$
      Answer:
      
      $$(a+b)^m = \sum_{i=0}^m {m\choose i} a^{m-i} b^i$$
      
      
      Set $a=1$ and $b=4$, we get $\sum_{i=0}^m {m\choose i} 4^i$. Therefore answer = $5^m$
   2. $$\sum_{k=0}^n (-1)^k{n\choose k} 3^{2n-2k}2^{2k}$$
      Answer:
      
      $$\sum_{k=0}^n (-1)^k{n\choose k} 3^{2n-2k}2^{2k} = \sum_{k=0}^n {n\choose k} (3^2)^{n-k}(-2^2)^{k}$$
      
      
      
      
      $$(a+b)^n = \sum_{k=0}^n {n\choose k} a^{n-k} b^k$$
      
      
      Set $a=3^2$ and $b=-2^2$, we get $\sum_{k=0}^n {n\choose k} (3^2)^{n-k}(-2^2)^{k}$ Therefore answer = $(3^2-2^2)^m = 5^m$