Summermath Homepage

Foundations of Mathematics
Summer Program for High School Students
Columbia University -- July 2001 -- Blumberg
Homework Set #1 -- Selected Answers

1. Any number of rules are possible here, the lesson being that simple rules of addition and multiplication can imply structural limits in the sequence. One example of a rule that easily eliminates the possibility of 7s and/or 8s is to multiply successive digits (as we did with the sequence we did in class), and then divide the product by 7, writing the remainder as the next digit in the sequence.

2. This problem draws on our discussion of the basic elements of computational geometry, in week #1.

a. (1 point) Triangulating the polygon produces 8 triangles (i.e. n-2 triangles) and thus the sum of the interior angles can be calculated as 9 * 180 degrees. This will of course be the answer for any 10-sided polygon, since the number of triangles here depends not on the particular shape of the polygon but only on the number of sides.

b. (1 point) In our discussion of Klee's theorem we realized, after triangulating a polygon, that the vertices of the polygon were 3-colorable (i.e. with only three colors we could color each of the vertices such that no two adjacent vertices were the same color). Since a guard stationed at any of the vertices of a triangle can see all of the interior of that triangle, it follows that, for any polygon, we'll need the floor of n/3 stationary guards to observe the interior of that polygon. In this case that number is 3 and in this particular example 3 guards are necessary and sufficient to guard the "gallery."

c. (1 point) If n is divisible by 3, the fact that the guards cannot see more than 180 degrees around them doesn't change the fact that n/3 guards suffice, since for any given triangle each of the interior angles must be less than 180 degrees. In our 10-sided example, however, things are slightly trickier, because after 3-coloring the vertices we see that the color that is represented only 2 times (as opposed to 3 times) is the one at vertices "covering" more than 180 degrees. For two of these three "concave" or "reflex" vertices, we can substitute a vertex of a different color that will "see" the same area and that has an interior angle less than 180 degrees (i.e. a convex vertex), but for one of the reflex vertices we cannot find such a substitute. At the same time, we notice that 3 guards are sufficient to cover the area of the polygon even with the 180 degree requirement. There is obviously an interesting question looming here: can we prove that the 180 degree constraint doesn't change the "floor of n/3" rule?

3. (2 points) Thinking of the problem in terms of graph theory, we know that there are only 3 vertices, and since the number of vertices with odd degree must always be even, we know that either all three vertices have an even degree, or exactly two have an odd degree, no matter how many edges are involved. Therefore, from the analysis of graphs in week #1, or perhaps from just analyzing the finite possibilities in this example, we know that however we configure the three land masses with bridges it will be possible to trace the figure, without lifting the pen(cil) and while tracing each line once and only once.

4a) In any social network with two or more persons, there are at least two persons with the same number of friends (where "friendship" is defined as a mutual & one-to-one relationship).

4b) For all positive integers n:
1 + 3 + 5 + 7 + ............. + (2n-1) = n^2

We can prove this using either direct proof or mathematical induction. Here is the direct proof:

4c) For all positive integers n:
1^2 + 2^2 + .....+ n^2 = [n(n+1)(2n+1)] / 6

4d) For k > 0, all integers of the form (2^[3k] - 1) are divisible by 7.

4e). In any planar (i.e. 2-D) connected graph, the number of vertices minus the number of edges plus the number of regions must be equal to two; i.e. V - E + R = 2.

I. As a first case, we'll consider a graph with 2 vertices connected by 1 edge. Note that this makes a single region of space (around the edge and vertices), so V-E+R = 2.

II. If V-E+R=2 holds for a given 2-D graph, then it will hold for the "next" graph, by which we mean the graph obtained by adding an edge. The reason is that when an edge is added, either: a) it connects one of the existing vertices with a new vertice, which causes the number of edges to increase by 1, the number of vertices to increase by 1 and the number of regions to remain constant; or b) it connects two existing vertices, causing the number of edges to increase by 1, the number of vertices to remain constant, and the number of regions to increase by 1. In either case the relation V-E+R = 2.

(Proofs in 4 were worth two points each.)

Summermath Homepage Summermath Reference Page
© 2001 Roger B. Blumberg