Homework #5

Problems from the text:

4.5: 3,8,11,12
4.6: 9
6.4: 3,8

Additional problems:

1. Using the Grobner basis technique from class (and of course, a computer algebra system), prove that Euler's nine point circle theorem is true. You may use either the fraction field method, or the saturation method to do this problem, but since the conclusions do not follow strictly from the hypotheses, you must use one or the other. A nice picture and discussion of the theorem is available here.

The statement is the following. Let ABC be a triangle. Then the midpoints of the sides, the feet of the altitudes, and the midpoints of the line segments joining the orthocenter (which is the intersection of the altitudes) and the vertices of the triangle, all lie on a single circle. The circle theorem of Appolonius is Euler's theorem in the case of a right triangle.

When I worked this problem out, I had 3 'u' variables, and 20 'x' variables, and therefore 20 'hypotheses'. There should be six 'conclusions' that you have to check. One way to proceed would be to consider the circle that goes through the midpoints of the sides, and show that the other 6 points are on this circle.

2. a) Using a computer algebra system, show that the graph with edges {(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,6),(3,9),(5,6),(6,8),(7,8),(8,9)} is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring.
b) Show that if you add a new edge {(1,3)} to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

3) Use the method of linear programming we learned in class to solve the following system of equations in the nonnegative integers:
3s_1+2s_2+s_3+2s_4=10
4s_1+3s_2+s_3=11
2s_1+4s_2+2s_3+s_4=10