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:
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.
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".):
b.
For all positive integers n:
c.
For all positive integers n:
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.