The Assignment
(Please do not consult outside sources,
except your notes and text, unless otherwise stated.)1. [7] What is the surround number of each of the regular n-gon, for each n in the set {3, 4, 5, ...}?
[10] What is the surround number of an isoceles right triangle?
2. If you check out this ancient theorm of Pappus, you find a nice figure in which A, B and C lie in that order along their line, and D, E and F lie in that order along their line. Let's see what happens if they don't: (For this problem, feel free to follow the links from the Pappus Page however you wish; but if you use anything you find on child pages, please cite it in your write-up.)
a. [5] State the dual theorem to Pappus' Hexagon Theorem. Recall that the notion of "between" for lines through a point depends on the location of the origin.
b. [8] Draw a picture of this dual theorem in action, labeling the origin and the lines A, B, C, D, E and F; and pointing out the conclusion of this dual theorem (pun intended) In your picture, make sure B is between A and C, and that E is between D and F.
c. [5] Ignore for the moment the fact that your figure in part b. was the dual of anything, and consider it in its own right as a theorem about points and lines. Move the origin to some other location (not on one of our lines). Is the theorem still true?
d. [5] Finally, show how to use duality to argue that regardless of the order of the points A, B and C along their line and D, E and F along their line, we will still have X, Y and Z collinear. (AE meets BD at X, AF meets CD at Y, and BF meets CE at Z)
3. [12] Here is a planar graph with its edges colored red and blue:
4. [3 each] We will now prove the above theorem. Given any planar graph, let:
- V denote the number of vertices
- E denote the number of edges
- F denote the number of faces
- fi
denote the number of faces which have i
edges on their boundary. (Note that if a face touches both sides
of an edge, then that edge counts twice on the boundary of its
face. This doesn't happen in the example above, but the tree
shown above (in the other column) has one face which is considered to
have 14 edges on its boundary.)
- c denote the
number of corners where color switches occur (A corner is a pair of
adjacent edges around a face.)
- D denote the number of definitions in this problem.
a. Show that under any 2-coloring of the edges of a planar graph, we must have:
c <= 2f3 + 4f4 + 4f5 + 6f6 + 6f7 + 8f8 + 8f9 + ....
b. Explain why
2E = 3f3 + 4f4 + 5f5 + 6f6 + 7f7 + 8f8 + 9f9 + ....
c. Explain why
F = f3 + f4 + f5 + f6 + f7 + f8 + f9 + ....
d. Use Euler's formula to show that
4V >= 2f3 + 4f4 + 6f5 + 8f6 + 10f7 + 12f8 + 14f9 + ....
e. Show that the average number of color switches at a vertex is less than 4.
f. Prove that there must be some vertex with at most 2 color switches.
5. Here are a robot and an obstacle. (Here is a full-size image.)
b. [3] Now draw the delooped boundary, indicating the connected components in which the robot may move freely.
6. [10] It is possible to alter just one of the lands of Zenopia to obtain a map with 10 regions, each of which has as a border the line segment in the middle of the map. Show how.
7. [10] MOMA calls Mona and asks if she'll help design their new art gallery. "Sure," she says. "Great," they say, "our only requirement is that the gallery be convex, with a single convex hole." But what MOMA didn't know was that Mona was on the board of directors of the local security service. So aside from satisfying their requirements, her only design principle will be to have the gallery require as many guards as possible. How large can this number be? Your answer should be accompanied by proof.
Some Definitions
Regular Polygon
A polygon whose sides are all the same length and whose angles all have the same measure. For example, a square, an equilateral triangle or a stop sign.
Isoceles Right Triangle
A triangle with a 90-degree angle and the two shorter sides of equal length.
Planar Graph
A graph which can be drawn in the plane with no crossing edges
Tree
A connected graph with no cycles, such as this one:
Some Questions
Q1 On #7 the outside polygon has to be convex but does the hole also have to be convex or can it take on any shape we want?
A1: The hole must be convex. Thanks for asking!
Q2: Rob, in problem two, where is the origin? I can see how order doesn't matter (after drawing it out), but I don't know what you mean by moving the origin around.
A2: One of the points of the problem is that the placement of the origin is arbitrary, which fact alone can be used to prove theorems, such as the one being addressed in problem 2.