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).
II. if in a social network of n persons, at least two persons have the same number of friends; then in a social network of (n+1) persons at least two persons will have the same number of friends. The reason is that either: i) If the additional person has no friends in the network, then we already know that at least two persons have the same number of friends in the n-person network, so the induction step is true; or ii) If the additional person has 1 or more friends in the network of n+1 persons, the number of friends each person in the network can have can only range from 1 to n (since we don't consider the case of people being friends with themselves). Therefore, there are only n different "friend numbers" (in graph theory: degrees) distributed among n+1 different friends (in graph theory: vertices), so at least two of the friends must have the same number of friends.
Therefore, In any social network with two or more persons, there are at least two persons with the same number of friends.
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:
1 + 3 + 5 + 7 + ...... + (2n-1) = SUM
(2n-1)+(2n-3)+(2n-5)+(2n-7)+ ...... + 1 = SUM
---------------------------------------------------
2n + 2n + 2n + 2n + .......+ 2n = 2(SUM)
n(2n) = 2(SUM)
[n(2n)]/2 = SUM
Therefore, the sum is equal to: (2n^2)/2 or simply n^2.
4c)
For all positive integers n:
1^2 + 2^2 + .....+ n^2 = [n(n+1)(2n+1)] / 6
I. for n=1 1^2 = [(1)(2)(3)]/6 = 1
II. if 1^2 + 2^2 + 3^2 + .... + n^2 = [n(n+1)(2n+1)] / 6
then 1^2 + 2^2 + 3^2 + .... + n^2 + (n+1)^2 = [(n+1)(n+1+1)(2(n+1)+1)]/6
The difference between the left sides of the equations: (n+1)^2, can
be shown to be equal to the difference between the right sides of the
equations: [(n+1)(n+2)(2n+3)]/6 - [n(n+1)(2n+1)]/6; so the induction
step is true.
Therefore, for all n >= 1, 1^2 + 2^2 + 3^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.
II We need to show that if 2^[3k] -1 is divisible by 7, then 2^[3(k+1)] - 1 is also divisible by 7.
To prove the inductions step it is sufficient to show that the difference between 2^[3(k+1)] - 1 and 2^[3k] -1 is itself divisible by 7. We find:
2^[3(k+1)] - 1 - (2^[3k] -1) = 2^[3k+3] - 2^[3k] = 2^[3k] (2^3 - 1) = 2^[3k] (7)
which is clearly divisible by 7. Therefore the induction step is proved, and so, combining both steps of the proof, we know that 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.)
