Closed book. You may have one page of notes to yourself to refer to. Please turn that page in along with your exam.

The questions are not equally difficult, but each is worth 20%.

(Note added with solutions.) Questions 1, 2 and 5 are exactly like questions discussed in class and asked and answered on homeworks, so 60% turns out to be just about the minimal passing grade.

Remember, as usual, that a solution is an argument expressed in complete sentences, not a number or a string of mathematical symbols.

1. How many strings of length 10 on the alphabet {x, y} contain
   • exactly 2 x's? There are C(10,2) = 10*9/2 = 45 ways to choose the two places in which to put the x's.
   • at least 2 x's? There are C(10,1) = 10 ways to use one x and just C(10,0) = 1 way to use none. So the other 2^10 - 10 - 1 = 1013 ways use at least two. If you did this the long way: C(10,2) + C(10,3) + ... + C(10,10) and got the right answer you lost a point or two for working too hard.
   • at most 8 x's? At most 8 x's happens just as often as at most 8 y's, which is the same as at least 2 x's, so the answer is the same as the answer to (b): 1013. You lost a point or two for doing the work all over again when you might have noticed that I'd really asked the same question twice.

2. How many different strings can be made from the letters in "MASSACHUSETTS", using all the letters?

   13!/2!2!4!. The denominator corrects for overcounting caused by the repeated letters. This is just like 342/30, which was part of question 5 on hw4. The solution is posted.

3. Let B be the set of bit strings of length 4 and f be the function from B to {0, 1, ..., 40} that assigns to each bit string the number that string represents in base 3.
   1. Compute f(1010).

      	f(1010) = 1*33 + 1*3 = 30
      	

   2. Is f one-to-one? Yes, because the base 3 representation of an integer is unique.
   3. Is f onto? No. The base 3 expansion of 6 is "20", which is not in B. So 6 isn't in the range of f . You can answer the question another way. B has 16 elements, and {0, 1, ..., 40} has 41, so there is no way f can be onto.

4. Let A be a nonempty finite set. Prove or disprove: there are exactly as many subsets S of A with |S| even as with |S| odd.

   This is true. Some people missed it because they could not read the question. Others missed it because they thought 0 was not an even number. It was hard to decide how much part credit to give in that case.

   Here are several solutions.

   Start with a few simple examples. If A = { x, y, x } then it has 8 subsets. Four of them have an odd number of elements: {x}, {y}, {z} and A itself. Four have an even number of elements: the empty set, {x,y}, {y,z} and {x,z} . So the theorem is true in this case. If A = {#,*} then the two subsets {#} and {*} have odd size and the other two (the empty set and A itself) have even size. So in this example too the number of subsets of even size is the same as the number of subsets of odd size.

   (Note that if A is empty it has just one subset, itself, which is of even size, and no subsets of odd size so the assertion is false.)

   If |A| happens to be odd then there's a really easy proof of the theorem. Since |S| is even just when the size of the complement |A-S| is odd we have a natural bijection between the even subsets and the odd ones, so there must be the same number of each.

   Unfortunately, this proof doesn't work when |A| is even. Here are two which do.

   The first one we build by remembering one of the ways we proved that |P(A)| was 2 |A| - we thought about what happened when we added one element to a set and noted that we found all the subsets of the enlarged set by looking at the subsets of the original with and without the new element. When we do that, the ones that were of even size stay even, but become odd when we add the new element, and vice versa. So once we know there were the same number of odd as even subsets of A we know there are the same number of odds and evens for the enlarged A.

   The second proof works by starting with the observation that when |A| = n the number of subsets of A of even size is C(n,0)+C(n,2)+... and the number of odd size is C(n,1)+C(n,3)+... . Now the binomial theorem says

   	0 = (1 - 1)n
   	  = C(n,0) - C(n,1) + C(n,2) - C(n,3) + ...
   

   and the equality we want follows easily.

   That identity was discussed in class. It's written down explicitly on page 229 of Rosen.

5. A true story. The first grade class at the J. P. Manning Elementary School is learning the beginnings of arithmetic. On October 19 the teacher, Cynthia Terry-Edd, asked her students to look for combinations of numbers of dogs, cats and rabbits that total 12 pets. The kids rapidly found 7+1+4, 3+6+3, and others. After class I asked her if she thought she could figure out how many combinations were possible, so she'd know when the kids had found them all. She's not a mathematician, but was excited by the idea of trying. I told her I'd ask you, on this exam. So do it. (You don't have to write an argument that she could follow. But you do need to write one for me. I echo Ms. Terry-Edd, who regularly tells her students "I need more words!". Just the answer isn't sufficient.)

   This is just like the pennies/nickels/dimes question discussed in class and the croissants question 5 (Rosen 342/10) on the homework. There are C(14,2) = 91 ways to insert the two dividers for the three categories. (No one pointed out that 91 is interesting because it's the only number less than 100 that looks like a prime but isn't. I was prepared to give a point or two of extra credit for that.)