Answers  to Review Questions for Prelim II

CS 280 - Fall 2002

The solutions to problems 19a, 19b, 21b, and 21c have been corrected.  In problems 19a and 19b, the solution assumed that CORRECTNESS has 12 letters.  Since it actually only has 11, the former answers were wrong.  In 21b, the reasoning was correct, but some numbers were wrong; the numbers have been corrected (the solution is now n instead of n+2).  An alternate solution to 21b has been added.  In 21c, the initial value for A(0) was wrong (it was 0 instead of 1); although the pattern for a 2-by-0 board uses no dominos, it does have one pattern of dominos that covers the board, so A(0) should be 1.

The exam takes place in class on Friday, November 8. I will try to arrive early so that we can start right at 1:25pm. Prelim II is designed to be somewhat shorter than Prelim I, so I expect to stop the exam and collect all the papers soon after 2:15pm.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material from readings and lecture through Monday, November 4.  Exams are cumulative, but you should expect to see problems drawn primarily from material covered since Prelim I. See the Schedule for a list of topics covered in lecture and for the corresponding readings.  The exam will attempt to gauge your knowledge and understanding of course concepts. You shouldn't need to memorize long proofs given in the text or in class (although you should understand such proofs).

The review questions given here are not meant to exhaust the possible topics for exam questions.  Consider reviewing both the homework assignments and the appropriate sections of the text.

Most of these questions are from exams given in previous incarnations of cs280.

Please let me know via email (chew@cs.cornell.edu) if you discover mistakes in my solutions.  Past experience indicates that I may have made some.

  1. The English alphabet contains 5 vowels and 21 consonants.
    1. How many strings of 6 lowercase English letters contain exactly 2 vowels if each letter can be used as often as you like?
      There are C(6, 2) ways to choose the positions for the two vowels.  There are 52 ways to assign vowels to those positions and 214 ways to assign consonants to the remaining positions.  The final answer is thus 52214C(6,2).
    2. How many strings of 6 lowercase English letters contain exactly 2 vowels if no letter is allowed to be used more than once?
      As before, there are C(6,2) ways to choose position for the two vowels.  There are 5*4 ways to assign vowels to these positions and 21*20*19*18 ways to assign consonants to the remaining positions.  The final answer is thus C(6,2)*5*4*21*20*19*18.
  2.  
    1. What's the minimum number of people that must be chosen to be sure that at least 2 have the same first initial?
      There are 26 possible first initials, so we must have two with the same initial if we have 27 people.
    2. What's the minimum number of people that must be chosen to be sure that at least 3 have the same birth month and were born on the same day of the week (Sat, Sun, Mon, etc.)?
      There are 12*7=84 (month, day) pairs.  Each such pair corresponds to a "pigeonhole".  Two people in each hole would require 168 people.  Thus, if we have 169 people there must be at least one pigeonhole with 3 people in it.
    3. Suppose there are 50 people with ages between 1 and 98 (1 and 98 are allowed).  Show that either there are 2 people with the same age or two whose ages are consecutive integers.
      Create 49 pigeonholes by pairing adjacent numbers starting with (1,2) and ending with (97,98).  Since there are 50 people, at least one pigeonhole has two people in it.  These two people are either the same age or their ages are consecutive integers.
  3.  
    1. How many bit strings contain exactly six 0's and nine1's if every 0 must be immediately followed by a 1?
      Since every zero is followed by a 1, you can think of "01" as a single unit; call this unit z.  The question can now be rewritten as: How many strings contain exactly 6 z's and 3 1's?  Thus there are 9 slots to fill and 3 of them must hold 1's.  This is just C(9, 3).
    2. How many solutions are there to the equation x1 + x2 + x3 + x4 = 35, if each xj is a positive integer (i.e., 1 or bigger)?
      This can be thought of as 4 bins into which we must distribute 35 stars given that each bin must hold at least one star.  The 4 bins correspond to 3 bars.  Four stars are used to ensure that each bin has at least one star.  This leaves us with C(3+31, 3) = C(34, 3) possible star/bar strings.
  4.  
    1. Find the number of elements in A1 U A2 U A3 if there are 100 elements in each set and there are 25 common elements in each pair and 10 elements in the intersection of all 3 sets.
      Use Inclusion/Exclusion. |A1 U A2 U A3| = |A1| + |A2| + |A3| - |A1 int A2| - |A2 int A3| - |A1 int A3| + |A1 int A2 int A3| where int is being used to represent the set-intersection operation.  So the answer is 100 + 100 + 100 - 25 - 25 -25 + 10 = 235.
    2. Suppose an experiment consists of choosing one of the elements of A1 U A2 U A3 at random with equal probability (where these three sets have the number of elements and intersections as given in part (a)).  Are the events A1 and A2 independent?
      By definition, A1 and A2 are independent if P(A1 int A2) = P(A1)*P(A2).  We size of our universe is 235, so P(A1 int A2) = 25 / 235 and P(A1) = P(A2) = 100 / 235.  Thus, we compare 25 / 235 with (100 / 235)2.  These are different, so the events are not independent.
  5. The dice in question are standard six-sided fair dice, and rolling a number with more than one die refers to the sum of the numbers showing on the dice.
    1. What is the probability of rolling a 5 with 2 dice?
      There are 4 ways to roll a 5 ((1,4), (2,3), (3,2), (4,1)) out 36 equally likely possible rolls, so the probability is 4 / 36 = 1 / 9.
    2. What is the probability of rolling a 5 with 3 dice?
      You need two ones and a three or you need one one and two twos to roll a 5.  Each of these can be rolled in 3 different ways, so we have 6 / 63 or 1 / 36.
  6. What is the expected sum that appears on 2 dice, where each of the dice is biased so that 3 appear with probability 0.3 and the other 5 numbers all have equal probability?  (For this problem, do the arithmetic to determine the expected value as a number.)
    The expected value for one die is 0.3*3 + (0.7 / 5) * (1 + 2 + 4 + 5 + 6) = 0.9 + 0.14*(18) = 3.42.  For two dice we would have the sum of two such values or 6.84.
  7. How many strings of length n=6 have two consecutive zeros?  Three consecutive zeros?  Four consecutive zeros?
    Let N(i) represent the number of valid strings of length i (i.e., those with two consecutive zeros).  Observe that all valid strings of length i can be divided into three disjoint groups: (1) those that begin with 1, (2) those that begin with 01, and (3) those that begin with 00.  Further we know how many strings are in each group:
    # that begin with 1 = N(i-1) because there must be a 00-pair in the remaining string,
    # that begin with 01 = N(i-2) because there must be a 00-pair in the remaining string,
    # that begin with 00 = 2i-2 because all such strings are valid.

    This gives us a recurrence relation: N(i) = N(i-1) + N(i-2) + 2i-2.  We can "start" the recurrence relation by observing that there are no strings of length 0 or 1 that have two consecutive zeros and there is exactly one string of length 2 with two consecutive zeros.  In other words, N(0) = N(1) = 0 and N(2) = 1.  Using the recurrence relation we can fill in the following table.
    i 0 1 2 3 4 5 6 7
    N(i) 0 0 1 3 8 19 43  94
    So the answer is 43.

    Alternately, you can determine how many strings have no consecutive zeros and then subtract.  The number of strings with no consecutive zeros is
    1 string with no zeros +
    6 strings with one zero +
    C(5, 2) = 10 strings with two zeros [the two zeros make 3 bins; the center bin has at least one 1 in it] +
    C(4, 1) = 4 strings with three zeros [the three zeros make 4 bins; the center two each have one 1] =
    21 strings with no consecutive zeros.
    Since there are 26 = 64 strings of zeros and ones, this leaves 43 strings containing two (or more) consecutive zeros.

  8.  
    1. Prove by induction that 7n − 2n is divisible by 5 for all positive integers n.
      Define P(n) as 7n-2n is divisible by 5.
      Basis: P(1) holds since 71 - 21 = 5 which is divisible by 5.
      Induction Hypothesis: P(k) holds; thus, 7k - 2k is divisible by 5.
      Consider 7k+1 - 2k+1.  We can rewrite this as
      7k+1 - 2k+1 = 7(7k - 2k) + 7(2k) - 2(2k) =  7(7k - 2k) + 5(2k).
      The first term is divisible by 5 by the Induction Hypothesis.  The second term obviously has a factor of 5.  Since both terms are divisible by 5 the whole expression is divisible by 5.
      Thus P(n) holds for all positive n.
    2. What is wrong with the following "proof"? 
      Let A(n) be a proposition "any n numbers are equal". We establish A(n) for all positive n by induction.
      BASIS STEP: A(1) states that one number is equal to itself, which is obviously true. 
      INDUCTIVE STEP. Suppose A(k), i.e., any k numbers are equal (the induction hypothesis). Take an arbitrary set X of k + 1 numbers and remove one of them, say a. By the induction hypothesis, all numbers in the remaining set X−{a} of k numbers are equal to each other. Remove another element b from X. By the induction hypothesis, all numbers from X−{b} are also equal. Therefore all numbers from X are equal to a and to b.
      The induction fails when |X|=2.
  9.  
    1. A soccer team has 20 women in the roster; two of them are goalkeepers. One goalkeeper and 10 field players make a team. How many ways are there to combine a team from those in the roster?
      There are 2 possible goalkeepers and then C(18,10) ways to choose the remaining field players.  The final answer is 2*C(18,10).
    2. Find the coefficient of x4y7 in (3x − 2y)11.
      From the Binomial Theorem, the coefficient is C(11, 4)34(-2)7 = -C(11, 4)3427.
    3. How many ways are there to order letters in the word NEVERTHELESS?
      If the letters were all different, the answer would be 12!, but E occurs 4 times and S occurs twice, so we have to divide by the number of permutation of 4 and 2 items.  The final answer is 
      12! / (4! 2!).
    4. How many solutions are there to the inequality x + y < 19 where x and y are nonnegative integers with x < 15 and y < 15?
      We can change the problem into one involving equality by observing that a solution to x + y < 19 is also a solution to x + y + z = 19, and vice versa.  We now have 19 objects to distribute into 3 bins (i.e., 19 stars and 2 bars), so there are C(21, 2) solutions, but this doesn't take into account the restriction that we want both x and y to be < 15.  We can count how many solutions fail this restriction.  We can start with 16 stars in the x-bin; this leaves 3 more stars to place into 3 bins or C(5,2) solutions.  There are the same number of solutions with 16 stars in the y-bin and these sets of solutions are disjoint.  Thus the final answer is C(21, 2) - 2*C(5, 2) = 210 - 20 = 190.
  10. In bridge, the 52 cards are dealt to four players.
    1. How many different ways are there to deal bridge hands to four players?
      C(52, 13) * C(39, 13) * C(26, 13) * C(13, 13) = 52! / (13!)4.
    2. What is the probability that all four aces went to one hand?
      There are C(48, 9) * C(39, 13) * C(26, 13) * 1 ways for all 4 aces to be in the first player's hand.  Thus there are 4 times this many ways to get all 4 aces into one hand.  The resulting probability is
      4 * C(48, 9) / C(52, 13).
    3. Assume that the player number one got a hand without aces. What is the probability that there is a player who has a hand containing all four aces?
      Restating the question: Find P(a player has all 4 aces | player 1 has no aces).  By the definition of conditional probability, this is the same as
      P(a player has all 4 aces and player 1 has no aces) / P(player 1 has no aces).  From (b), the numerator is 3 * C(48, 9) / C(52, 13).  The denominator is 
      [C(48, 13) * C(39, 13) * C(26, 13)] / [C(52, 13) * C(39, 13) * C(26, 13)].  The denominator can be rewritten as C(48, 13) / C(52, 13).  The final answer is thus 3 * C(48, 9) / C(48, 13).
  11. A pair of fair dice is rolled.
    1. What are the expected values of the minimum m and the maximum M of numbers on the dice?
      There are 11 ways to roll 2 dice that result in a minimum of 1; thus, the P(m=1) = 11/36.  Similarly, P(m=2) = 9/36 and P(m=3) = 7/36 and P(m=4) = 5/36 and P(m=5) = 3/36 and P(m=6) = 1/36.  The expected value of m is thus 11/36 + (2)9/36 + (3)7/36 + (4)5/36 + (5)3/36 + (6)1/36 = [11 + 18 + 21 + 20 + 15 + 6] / 36 = 91/36.  Using similar reasoning, the expected value of M is (1)1/36 + (2)3/36 + (3) 5/36 + (4)7/36 + (5)9/36 + (6)11/36 = [1 + 6 + 15 + 28 + 45 + 66] / 36 = 161 / 36.
    2. Are the random variables m and M independent?
      No.  To be independent, we would need P(m=1 and M=1) = P(m=1) * P(M=1).  But P(m=1 and M=1) is 1/36, while P(m=1)*P(M=1) = (11/36) * (1/36).  These are clearly not equal.
    3. Find the expected value of m + M.
      We know from properties of expected value that E(m+M) = E(m) + E(M).  Thus the answer is (91 + 161) / 36 = 252 / 36 = 7.
    4. Find the expected value of m * M.
      Since m and M are not independent, it is not the case that E(m*M) = E(m)*E(M).  One way to work out this problem is to laboriously go through all the probabilities for the possible values of m and M.  There is, however, a shorter way.  Observe that m*M is the same as X*Y where X is the value on one die and Y is the value on the other.  Note that even though m and M are not independent, X and Y are independent.  Thus E(m*M) = E(X*Y) = E(X) * E(Y) = (7/2)(7/2) = 49/4.
  12. How many positive integers with five digits or less have neither their first digit equal to 3 nor their last digit equal to 5?
    There are 105 -1 positive integers with 5 or fewer digits (the -1 is needed because 0 is not a positive integer).  Of these, there are 104 that have 5 digits and have their first digit equal to 3; 103 that have 4 digits; 102 with 3 digits; 10 with 2 digits and 1 with 1 digit.  Thus, there are 11111 numbers with their first digit equal to 3.  There are 104 numbers with 5 or fewer digits that have there last digit equal to 5.  This is almost all we need, but we also need to determine how many number have both their first digit equal to 3 and their last digit equal to 5.  There are 103 such number with 5 digits, 102 with 4 digits, 10 with 3 digits, and 1 with two digits; 1111 all together.  Using inclusion/exclusion, the final answer is 99999 - 11111 - 10000 + 1111 = 79999.
  13. How many positive integers are there less than 10000 such that the sum of their decimal digits is 12?
    This can be restated as: How many solutions are there to w+x+y+z = 12 where each variable is a nonnegative integer < 9?  If we ignore the < 9 restriction, there are 4 bins (i.e., 3 bars) and 12 stars, giving C(15, 3) solutions.  We have to subtract those solutions that include a value greater than 9.  We can put 10 stars into the w-bin, leaving 2 stars to distribute among the 4 bins; thus, there are C(5, 2) solutions where w>9.  Similarly, there are C(5, 2) = 10 solutions where x > 9, 10 solutions where y>9, and 10 solutions where z>9.  Further all of these solutions are disjoint.  Thus the final answer is C(15, 3) - 4*10 = 455 - 40 = 415.
  14. A fair coin is tossed five times.  What is the probability of getting exactly four heads, given that at least one of the tosses is heads?
    P(exactly 4 heads | at least one toss is heads) 
    = P(exactly 4 heads and at least one toss is heads) / P(at least one toss is heads)
    P(exactly 4 heads and at least on toss is heads) = P(exactly 4 heads) = 5/32
    P(at least one toss is heads) = 1 - P(all tails) = 31/32
    Thus the final answer is 5/31.
  15. Some tribe values boys so much that each of their families keeps making kids until they get a boy (after which they relax and make no more kids). On the other hand, no family can a afford having more than five kids.  So if the first five babies in a family are girls, the family stops making children anyway.  Assuming that a boy and a girl are equally likely, consider two random variables X -“the number of boys in a family ”,Y -“the number of girls in a family ”. 
    1. Find the expected values E(X) and E(Y) and compare them.
      E(X) = (1/32)*0 + (31/32)*1 = 31/32
      E(Y) = (1/4)*1 + (1/8)*2 + (1/16)*3 + (1/32)*4 + (1/32)*5 = [8 + 8 + 6 + 4 + 5] / 32 = 31/32.
      The expected values are identical.
    2. Are X and Y independent?
      No.  Observe that Y=5 implies that X=0.
      In more detail, P(Y=5 and X=0) = 1/32 which is not the same as P(Y=5)*P(X=0) = (1/32)2.
    3. Find the expected value E(X+Y).
      This is just E(X) + E(Y) = 31 / 16.
  16. A small grocery store carries 400 items and does 1000 transactions in one day.  For three particular items (bananas, strawberries, and yogurt) we have the following data: Suppose we're interested in how fruit sales affect yogurt sales where fruit, for this store, is either bananas or strawberries.  Find the support and confidence factors for each of the following association rules:
    1. bananas -> yogurt
      Support = 25/1000 = 2.5%.
      Confidence = #(bananas, yogurt) / #(bananas) = 25 / 35 = 5 / 7.
    2. strawberries -> yogurt
      Support = 30/1000 = 3%.
      Confidence = #(strawberries, yogurt) / #(strawberries) = 30 / 45 = 2 / 3.
    3. bananas, strawberries -> yogurt
      Support = 10/1000 = 1%.
      Confidence = #(bananas, strawberries, yogurt) / #(bananas, strawberries) = 10 / 20 = 1 / 2.
    4. fruit -> yogurt
      For this one, we need to know how many transactions involve fruit.  We add #(bananas) to #(strawberries), but we have to subtract #(bananas, strawberries) to avoid overcounting (i.e., inclusion/exclusion).  Thus the total number of fruit transactions is 35 + 45 - 20 = 60.  Similar reasoning is used to determine #(fruit, yogurt) = #(bananas, yogurt) + #(strawberries, yogurt) - #(bananas, strawberries, yogurt) = 25 + 30 - 10 = 45.
      Support = 45/1000 = 4.5%
      Confidence = #(fruit, yogurt) / #(fruit) = 45 / 60 = 3 / 4.
  17. At a conference luncheon, each table is round and holds 8 people. Each person chooses one of beef, chicken, or vegetarian for their main course and chooses either pudding or sherbet for dessert. Each person also has a choice of three drinks: coffee, hot tea, or iced tea.
    1. What is the minimum number of tables that need to be considered to ensure that there are at least 4 people among those tables who have ordered the same main course, dessert, and drink?
      There are 3*2*3 = 18 ways to order main-course, dessert, and drink.  If each such meal is ordered by 3 people, this makes 3*18 = 54 people.  Thus if we have  more than 54 people, there must be some meal that is ordered by 4 or more people.  Since there are 8 people per table, we need 7 tables to reach a number larger than 54.  The answer is 7.
    2. Suppose beef is twice as popular as chicken, which is twice as popular as the vegetarian meal. If a person is selected at random from among those who attend the luncheon, what is the probability that that person chose beef?
      For each person who orders vegetarian there are two who order chicken and 4 who order beef.  Thus, for a random person, the probability that that person ordered beef is 4/7.
    3. Each waiter loads a tray with the 8 drinks needed for a given table. How many different sets of 8 drinks are possible?
      This is equivalent to placing 8 stars (the positions on the tray) into 3 bins (the three types of drinks).  The 3 bins are equivalent to 2 bars, so the solution is C(8+2, 2) = C(10, 2).
    4. One of the waiters claims that, at a particular table, there are no two adjacent people who ordered the same drink. How many possible sets of 8 drinks are there for such a table?
      This is possible for any set of 8 drinks except for those that contain 5 or more of one drink.  The idea is count how many sets of 8 drinks have 5 or more of a single drink and then subtract that amount from the answer in (c).  The number of sets with five or more of one drink (say, coffee) is equivalent to placing 5 stars into the coffee bin and then distributing the remaining 3 stars.  Thus there are C(5, 2) sets of drinks with 5 or more coffees.  We get the same number of sets for 5 or more teas and for 5 or more iced teas.  These sets are disjoint, so the final answer is C(10, 2) - 3* C(5, 2).
  18. A single, standard, 6-sided die is rolled 200 times. Let X be the number of times an even number is rolled and let Y be the number of times a 6 is rolled.
    1. Are X and Y independent? Explain.
      No.  Consider P(X=0 and Y=200).  This cannot occur so the probability is 0.  But P(X=0) * P(Y=200) = (1/2)200 * (1/6)200.  Since these probabilities are not the same, X and Y are not independent.
    2. Determine E(X) and V(X) (i.e., the expected value and the variance for random variable X)
      Define Xi as the number of even numbers on the ith roll.  E(Xi) = 1/2.  V(Xi) = E(Xi2) - (E(Xi))2 = (1/2) - (1/4) = 1/4.  We have E(X) = E( sum Xi) = 200*1/2 = 100.  Because the Xi are independent, we also have V(X) = V(sum Xi) = 200*1/4 = 50.

      Or: You can recognize that this is a Bernoulli-trial problem with p = q = 1/2.  E(X) = np = 200*p = 100.  V(X) = npq = 100 (1/2) (1/2) = 50.

    3. Determine E(Y) and E(X+Y).
      E(Y) = np = 200 (1/6) = 100/3.  E(X+Y) = E(X) + E(Y) = 100 + 100/3 = 400/3.
    4. Determine V(X+Y).
      Define Xi and Yi as the corresponding random variable for the ith roll and let Zi be their sum.  The Zi are all independent since the results of one roll have no effect on other rolls.  Zi has the value 0 if roll i is odd, the value 1 if roll i is 2 or 4, and the value 2 if roll i is 6.  Thus, E(Zi) = (1/2)(0) + (1/3)(1) + (1/6)(2) = 2/3 and E(Zi2) = (1/2)(0) + (1/3)(1) + (1/6)(4) = 1.  V(Zi) = E(Zi2) - (E(Zi))2 = 1 - (2/3)2 = 5/9.  Because the Zi are independent, we have V(Z) = V(sum Zi) = 200*5/9 = 1000/9.
  19. A, E, I, O, and U are vowels. For this question, the remaining 21 letters are considered to be consonants. When a letter is chosen at random from a string, assume that each position is equally likely to be chosen.
    1. How many different strings can be made from all the letters of CORRECTNESS?
      If all the letters were different there would be 11! strings, but there are 4 letters (C, R, E, and S) that appear twice, so we have to divide to avoid over-counting.  The final answer is (11!)/(2!)(2!)(2!)(2!).
    2. If 4 letters are chosen at random from CORRECTNESS without replacement, what is the probability that all 4 letters are consonants given that C was never chosen?
      The goal is to find P(all consonants | C never chosen).  By definition of conditional probability, we have P(all consonants | C never chosen) = P(all consonants and C never chosen) / P(C never chosen).  The numerator is (6/11)(5/10)(4/9)(3/8) and the denominator is (9/11)(8/10)(7/9)(6/8).  The final answer is thus (6*5*4*3) / (9*8*7*6).
    3. If 8 letters are chosen from CORRECTNESS with replacement, what is the probability that 2 or more of the chosen letters are the same?
      There are only 7 different letters, so if 8 letters are chosen there must be two the same (by the Pigeonhole Principle).  The probability is 1.
  20. At a certain school, a CS major must pick 5 courses from a list of 10. Out of these 10 there are two 2-course sequences. For a 2-course sequence, the first course of the sequence must be taken before the second.
    1. How many possible sets of 5 courses can be chosen to satisfy the requirements?
      If we ignore the sequence restrictions, there are C(10, 5) sets of courses.  Now we have to subtract the illegal sets.  A set is illegal if it contains the second course of a sequence, but not the first.  Let A and B represent the two courses in a sequence.  There are C(8, 4) sets that include B, but not A.  Let C and D represent the two courses in the other sequence.  There are C(8, 4) sets that include D, but not C.  We need to subtract these from C(10, 5), but we've over-counted courses that are illegal because of both B and D.  There are C(6, 3) sets that include both B and D, but neither A nor C.  Thus the final answer is C(10, 5) - 2*C(8, 4) + C(6, 3) = 132.

      Or: You can add the number of sets with no sequences to the number of sets with one of the sequences to the number of sets with both sequences.  There are C(8, 5) sets with no sequences.  There are 2*C(7, 3) sets with one sequence.  There are C(6, 1) sets with both sequences.  Adding these, we get 132.

    2. Suppose a student takes one course each semester for 5 semesters. Suppose further that the student takes one of the 2-course sequences (say, the one on algorithms), but does not take either course from the other 2-course sequence. With these restrictions, how many possible ways are there to schedule 5 courses over the 5 semesters? Note that a schedule with course X taken in semester 1 is considered to be different from a schedule with course X taken in semester 2.
      We have to choose courses for each of the 5 semesters.  We first choose 2 semesters to be the ones in which the student takes the sequence.  There are C(5, 2) ways to do this.  The sequence can be assigned to those 2 semesters in only one way since we can't change the order of the courses in the sequence.  The remaining three semesters are filled with the remaining 6 courses.  There are 6 possible courses for the first of these semesters, 5 for the next, and 4 for the last.  The final answer is thus C(5, 2)*6*5*4.
  21.  
    1. Given an n-by-n checkerboard, how many paths are there from lower-left to upper-right if the only moves allowed are one square either horizontally or vertically?
      Any such path is of length 2n-2 and consists of n-1 horizontal moves and n-1 vertical moves.  So we have 2n-2 moves n-1 of which must be chosen to be the vertical moves.
      C(2n-2, n-) possible paths.
    2. How many paths if you are not allowed to make two horizontal moves in a row?  (Two vertical moves in a row are OK.)
      There are two paths without any horizontal or vertical moves in a row (HVHVHV... and VHVHVH...).  If there are two V's in a row then the path must start and end with H and must alternate V's and H's except at a single double-V.  There is one alternating-VH path with n-1 H's and n-2 V's.  For each such path, we can choose any one V and replace it with a double-V to make a valid corner-to-corner path.  Thus there are n-2 paths with two V's in a row.  The total number of paths is thus n.

      Another way to do this same problem is to consider the n-1 H's to be bars dividing n bins. Since the H's are not allowed to be adjacent, we have to put at least n-2 V's so that there will be one V between each adjacent pair of H's.  This leaves one additional V that can be placed into any of the n bins.  Thus, there are n paths that avoid adjacent H's.

    3. For a 2-by-n checkerboard, find a recurrence for the number of ways to cover the board with 2-by-1 dominos.  A domino can be placed either horizontally or vertically.
      We can build a recurrence based on the position of the first domino.  Let A(n) be the number of ways to cover a 2-by-n board.  If the first domino is placed vertically then the remaining area to be covered is in the shape of a 2-by-(n-1) board, so there are A(n-1) ways to cover the remaining board.  If the first domino is placed horizontally then there is no choice except to place another domino directly below it, leaving a remaining area of size 2-by-(n-2); so there are A(n-2) ways to cover the remaining board.  Thus the total number of ways to cover the board is A(n) = A(n-1) + A(n-2).  To complete the solution, we need to specify initial values.  A(0) = 1 and A(1) = 1.
  22. Solve the following recurrence relations.
    1. an = an-1 + 6an-2; a0 =1, a1=2.
      Characteristic Equation: r2-r-6 = 0 with solutions r = -2 and r = 3.
      General solution: C1(-2)n + C2(3)n.
      Plugging in n=0 and n=1, we get C1 + C2 = 1 and -2C1 + 3C2 = 2.
      From this, we conclude that C1 = (1/5) and C2 = (4/5).
    2. an = 7an-1 - 10an-2; a0 =2, a1=1.
      Characteristic Equation: r2 - 7r + 10 = 0 with solutions r = 2 and r = 5.
      General solution: C1(2)n + C2(5)n.
      Plugging in n=0 and n=1, we get C1 + C2 = 2 and 2C1 + 5C2 = 1.
      From this, we conclude that C1 = 3 and C2 = -1.
    3. an = 6an-1 - 9an-2; a0 =0, a1=1.
      Characteristic Equation: r2 - 6r + 9 = 0 with solutions r = 3, multiplicity 2.
      General solution: C1(3)n + C2n(3)n.
      Plugging in n=0 and n=1, we get C1 = 0 and 3C1 + 3C2 = 1.
      From this, we conclude that C1 = 0 and C2 = (1/3).