Homework 5

CS 280 - Spring 2002

Due: Friday, March 8

Several problems in this homework assignment involve permutations and combinations.  For such problems, you do not have to multiply out all the factorials.  In other words, it's OK to write your answers in terms of C(n,r) or similar notation.

Part A

  1.  
    1. How many ways are there to rearrange the letters in the word COMPUTER?
    2. How many ways if you are required to keep the vowels in alphabetical order?  (In other words, the consonants can be in any order at all, but the vowels must appear in the order EOU, possibly with consonants in between the vowels.)
    3. How many ways if the the consonants must be kept in alphabetical order?
    4. How many ways if both vowels and consonants must be kept in alphabetical order?
       
  2. Given an arbitrary set of 10 integers, prove that there is a subset of these 10 integers whose sum is divisible by 10.  Hint: Consider sums of the form x1, x1+x2, x1+x2+x3,...

Part B

  1. Five points with integer coordinates are plotted on a graph.  Consider the midpoints of the segments that join these 5 points.  Prove that at least one of these midpoints has integer coordinates.
     
  2. Recall from lecture: There are C(10, 5)/2 ways to divide 10 people in to 2 teams of 5 each.
    1. How many ways are there to divide 15 people into 3 teams of 5 each?
    2. How many ways are there to choose two teams of 5 people each from 15 people?

Part C

  1.  
    1. You're driving back to Ithaca and approaching the tollbooth as you exit the NY Thruway when you notice that there are two lines waiting to pay the toll: one of the line consisting entirely of m cars; the other consisting entirely of n trucks.  Inspired by your love of cs280, you realize that you can find a formula for all the patterns by which the cars and trucks can leave the toll plaza.  What is this formula?  A pattern looks like C1T1C2C3C4T2... where Ci represents the ith car and Ti represents the ith truck.  You should assume that the cars remain in their current order and the trucks remain in their current order.  The only thing that can vary is when the attendant decides to release the vehicle.
    2. After leaving the tollbooth, you continue on your journey to Ithaca, arriving late at night and hungry.  You decide to buy a snack at P&C.  At P&C, there are three lines open.  There are people waiting in each line; in fact, there are p people in the first line, q people in the second and r people in the third.  Find a formula for the number of possible orders in which these p+q+r people leave P&C and give a brief explanation of why your formula is correct.  You should assume that if any line becomes empty then the checker immediately closes that line; thus, people do not change lines even if another line becomes empty.  Each person leaves the store as soon as they're checked out.
       
  2. The instructor for a small class (7 students) tells the students after an exam that if any 4 of them get together they'll have at least one correct solution to every problem.  He goes on to claim that if any 3 of them get together there will be at least one problem for which each of the 3 has an incorrect answer.  The exam has 30 questions.  Show that the instructor's claim must be incorrect.