Prelim II Solutions

CS 280 - Spring 2002

  1. (16 points; 4 each) 
    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).

  2. (16 points; 4 each)
    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.

  3. (9 points; 3 each) 
    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 12! 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 (12!)/(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/12)(5/11)(4/10)(3/9) and the denominator is (10/12)(9/11)(8/10)(7/9).  The final answer is thus (6*5*4*3) / (10*9*8*7).

    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.

  4. (10 points; 5 each) 
    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.