I hope some of the questions are easy. I suggest you do those first. Some are open ended - use your time wisely.

1. Draw n straight lines at random in the plane. "At random" means no two lines are parallel, and no three lines go through a single point. That's sometimes called "general position". These configurations have regions, vertices (where lines intersect) and edges. They're not quite the planar graphs we've studied, since some of the edges have just one vertex and "go off to infinity". Some of the regions do too.

   Here's a picture for n = 4.

   

   The following table enumerates some features for n = 2,3 and 4.

                           number of
           lines   vertices  regions   edges  
             2         1        4        4      
             3         3        7        9      
             4         6       11       16      
   

   1. Guess (and prove) the counts for n lines.

      Each pair of lines crosses just once, so counting vertices is the handshake problem we studied on the first day of class. There are C(n,2) = n(n-1)/2 vertices.

      The n-1 vertices on each line divide the line into n edges, so there are n*n = n² edges.

      Counting the regions is a little harder. There are several ways. Here's one. Let R(k) = the number of regions when there are k lines. Then R(1) = 2. If there are k lines drawn and you add one more, that line splits k of the existing regions in two, so R(k+1) = R(k) + k. That recursive formula says that

      	R(n) = 2 + 3 + ... + n 
      	     = 1 + (1 + 2 + ... + n)
                   = 1 + C(n+1,2)
                   = 1 + (n+1)n/2
      

   2. Is there an Euler-like formula for these configurations? If so, prove it.

      The Euler formula for these configurations is just V-E+R=1. To prove it, just do the algebra starting with the answers to (a).

   3. How many colors does it take to color the regions? (Proof, please.)

      "Coloring" means "color the regions". You can always do it with two colors. Suppose that's been done for n lines. When you add a line you can just reverse all the colors on one side of the line, changing some regions completely and changing pieces of the n regions that have been split.

      Alternatively, note that every vertex has degree four, so the dual graph is bipartitite and hence two-colorable.

   4. Can you count the unbounded regions?

      Yes. Each new line splits two unbounded regions, so the number of unbounded regions increases by 2, so for n lines there are 2n unbounded regions.

   5. Anything else interesting?

      Counting the unbounded regions and the bounded regions and proving the Euler formula are related problems. For example: if you remove all the unbounded regions and the unbounded edges then you have a graph that satisfies the Euler formula we know about. Since you know the number of vertices and edges, you can use that to compute the number of bounded regions. That allows you to compute the number of regions (add back the 2n unbounded ones) and to verify the Euler formula for the whole configuration.

2. Let

   	f(x,y,z) = (x + 3y + 5z)2008
   

   1. How many terms (expressions of the form dxaybzc) will there be if you multiply this out?

      There are as many terms as there are sums a+b+c=2008 with a, b and c nonnegative integers. We counted those in class (apples, bananas and cherries) and found the anser C(2010,2). You could have looked it up in your notes.

      Hardly anyone got this right. Some got close.

   2. What is the coefficient of the term x2005y2z1?

      There are 2008 ways to pick the factor that contributes the z and then C(2007,2) ways to choose the two factors that contribute the y's. So the answer is 2008*(2007*2006/2)*45. The 45 is the factor from the coefficients of y and z themselves.

   3. We've assumed (without stating it) that when you multiply out the expression the formal variables commute: xy = yx. What is the answer to part (a) if x, y and z represent matrices, for which multiplication may not be commutative.

      This is the number of 2008 letter words you can build from a three letter alphabet: 3²⁰⁰⁸.

   Here are some hints you shouldn't need - but I really want to read correct answers, so I'll provide them anyway. (If you didn't need them, let me know. If they helped, let me know that too.)

   • Try out whatever methods you use for the exponents 1 and 2 and perhaps 3 as well before you commit to answers for 2008.
   • We studied a problem like this in class. Remember apples, bananas and cherries?

3. Consider a game of Nim with 2008 piles, containing 1, 2, 4, ..., 2²⁰⁰⁷ chips.

   1. How many chips are there altogether?

      	1 + 2 + ... + 22007 = 22008 -1
      

      You ought to know the sum of that geometric series without having to think twice!

   2. What is the Sprague-Grundy value for the starting position?

      Since the SG value for a Nim pile is the number of counters in the pile, the SG value for this game is the nim sum of the powers of 2. But each of those powers of 2 has a single bit set in its own column, nothing cancels in the nim sum, which is just the string of 2007 1's. That's the binary representation of 2²⁰⁰⁸ -1, so the answer to (b) is the same as the answer to (a).

   3. What first move would you make in this game?

      Remove one chip from the largest pile, converting the SG value from 100...000 to 11...111. Then there are two 1's in each column when you look at all the piles, so the nim sum is 0: a P position.

4. Carefully state three definitions or theorems from this course that come with Leonhard Euler's name attached.

   The Euler phi function.

   Euler's theorem (from number theory).

   Euler paths.

   Euler's theorem on the existence of Euler paths (the Konigsburg bridge problem).

   You could look these up in your book or notes and get them right. Some of you didn't.

5. Find the greatest common divisor of 2008 and 4267 and write it as an integral linear combination of those two numbers.

   The Euclidean algorithm takes only two steps to show that gcd(2008,4267) = 251, and that 251 = 1*4267 - 2*2008.

6. How many integers between 1 and 2008 are relatively prime to 2008?

   From the previous problem, we know that 2008 = 8*251. 8 and 251 are relatively prime, and 251 is prime (you need to say that!) so

      phi(2008) = phi(8) * phi(251) = 4 * 250 = 1000.
   

   I was amused to find that out.

7. Let t(n) be the number of positive divisors of the integer n. For example, the divisors of 6 are 1, 2, 3 and 6 so t(6) = 4. t(n) = 2 if and only if n is prime.

   1. Complete the following statement and then prove it:

      	t(n) is odd if and only if ...
      

      			... n is a perfect square.
      

      Proof: The factors of n come in pairs d and n/d. They are equal only when d = n/d, so n = d². Only then is t(n) odd.

   2. Prove or disprove:

      	 If m and n are relatively prime then t(mn) = t(m)t(n). 
      

      This is true. To prove it, note that the divisors of a number correspond to subsets of the set of primes dividing that number (you need the fundamentatal theorem of arithmetic to prove that). When m and n are relatively prime, they have no prime factors in common. Now the theorem follows from the fact that there's an obvious one to one correspondence between the cartesian product P(A)X P(B) and P(A union B) when A and B ar disjoint. (That was a homework problem.)

   3. Compute t(2008).

      Use part (b) to conclude that t(2008) = t(8)*t(251) = 4*2 = 8. Or just list all 8 divisors of 2008.

8. If there's something in the course you're particularly fond of or spent lots of time studying that I didn't ask about, make up a question here and answer it.