Foundations of Mathematics
Summer Program for High School Students
Columbia University -- July, 2000 -- Blumberg
Homework Set #1 -- Due 7/14 (Friday), by noon.

1. Devise a rule for generating a single-digit infinite sequence (like the one we analyzed in class) but make your rule such that, no matter what numbers you start with, the numbers 7 and 8 will never appear (or never appear again if you start with 7 and/or 8). Your rule can be as simple or as complicated as you like, but it must make use of at least one arithmetic operation (i.e. addition, subtraction, multiplication, division).

2. Consider the following polygon:

a). Redraw the polygon on your own paper, and triangulate it. Write an expression for the sum of the interior angles of the polygon. Will this express the sum of the interior angles of any polygon with 10 sides?

b). (Klee's art gallery problem) In this polygon, how many stationary guards will be sufficient so that every point inside the polygon can be seen by at least one guard? Will this number of guards be sufficient to guard any polygon with the same number of sides as this one?

c). Suppose in addition to the constraint that the guards must be stationary, we add that they cannot see more than 180 degrees around them. Explain whether/why this constraint would change your answers in b) above.

3. Consider the following two statements, and write a brief essay (at least 2 pages) comparing the way we come to know that they are true. You might want to consider how you would prove or argue for each statement, how you would evaluate an article in the New York Times claiming that these statements were false, and under what circumstances you might change your mind about the truth or falsity of these statements.

• The square-root of 7 is an irrational number.
• More American soldiers were killed in the American Civil War than in any other war in which the United States has participated.

4. Suppose that someone has drawn a graph (i.e. a point and line drawing) consisting of 3 vertices and some number of edges connecting them. Assuming that there is at least one edge between any two of the vertices, but without knowing the exact number of edges in the graph, can you be certain whether or not it will always be possible to trace the figure in such a way that, while not lifting your pen/pencil from the paper, you can trace each line once and only once?

5. Prove two (2) of the following by direct proof and/or mathematical induction (note that "^" is used to indicate a superscript; for example, "n^2" should be read as "n squared".):

a. In any closed 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 and one-to-one relationship).

b. For all positive integers n:


1 + 3 + 5 + 7 + ............. + (2n-1) = n^2

c. For all positive integers n:


1^2 + 2^2 + 3^2+ 4^2 + ......... + n^2 = [n(n+1)(2n+1)] / 6

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

e. In any planar (i.e. 2-D) 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.