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

1. Consider the following polygon:

a). Triangulate the polygon, and 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 11 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 11 sides?

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.

2). 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.

3. Suppose you know that a particular city consists of three pieces of land, and several bridges connecting them. Assuming there is at least one bridge between any two of the land masses, can you say whether or not it will always be possible to devise a path through the city, that crosses each bridge once and only once, no matter how many bridges connect the pieces of land? Explain.

4. Prove at least two 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.