1. (a) First note that no two lines are parallel because every line intersects every other line, and no two lines are concurrent since each line only has a single intersection point with any other line. Also no three lines share the same point of intersecton.
Thus any line that intersectsa other lines is passing through a + 1 regions. If we label the lines in order on intersection from left to right (or down to up if the intersecting line is vertical), we have the region that precedes , and the regions that lie between each line and the next, and the region that follows making regions in all.
To show that n lines divide the plane into regions for every natural number n, we will use induction. First, though, we note that .
Now, for , clearly one line divides the plane into 2 regions and provides the right number. Thus the formula holds for n = 1.
Next, suppose the formula holds for n. That means the plane is divided into regions.
Now suppose an additional line is added to the plane so that it is not parallel to any of the previous lines and not passing through any intersection that already exists. This new line passes through regions dividing each into two distinct regions. In other words, by quantity, it adds
additional regions to the regions we already had.
Therefore the plane has now been divided into regions, and the formula is therefore true for every by induction.
1 (b) Using Induction:
For , there are two regions, color one regions color A and the other color B.
======
For purpose of induction, suppose that for any natural number n, the map for can be colored solely with color A and color B.
Now consider.
is at least 2, so there is at least one line that is not vertical. Remove that line from the map. The new map is determined by n lines and therefore can be colored solely with color A and color B. Consider this done.
Replace the removed line in its original position. Leave any colors below the line as they now are. For each region above the line, reverse the colors with color B replacing color A and color A replacing color B.
Now observe that each pair of newly formed regions (sharing a segment on the replaced line) are different colors.
The remaining regions are either
--- completely above the replaced line and still mapped using reversed colors A and B; or
--- completely below the replaced line and still mapped using the original colors A and B.
Therefore, no two abutting regions are the same color and all regions are either color A or color B.
Q.E.D.
2. Partition the integers into 3 sets: , and
Choose 5 integers.
Case 1: Three or more of these integers are from the same set, choose just three of these and their sum will be either 9n or 9m+3 or 9p+3, each of which is divisible by 3.
Case 2: No three integers are in the same set. That means each set must contain at least one of these integers. From each set, choose one of these integers. Their sum will be 3n + 3m + 1 + 3p + 2 = which is clearly divisible by 3.
Q.E.D.
3. ends in 8.
Proof:
is a perfect square and is odd since the product of odd numbers is itself an odd number.
Odd numbers take the form where nis an integer. If n is even, the n = 2k from some integer k. In that case which is impossible for a perfect square (see hint). Therefore n must be odd which means n = 2k + 1 for some integer k. Thus .
for some integer k.
However, has last digit 6 for all natural numbers.
And a natural number ending in 6 multiplied by a natural number ending in 8 will end in 8.
4. Following the suggestion in the problem set, we will make the following assumption for the sake of contradiction:
Assume there is an equilateral triangle with three vertices (0,0), and , where are all relatively prime integers. Let s be the length of each of the three equal sides.
Using the distance formula we get the following equations:
:
:
:
Now expand and simplify to get
:
Substituting from and into gives
: .
Rearrange and get:
:
Square both sides and get:
:
Now multiply the left and right sides of and and get
:
Use the transitive property with and to get
:
Subtract from both sides of to get
:
This can be expressed as
:
Because are relatively prime integers, we know and thus . Therefore we can divide both sides of by to get
: , which results in
:
But the left side of the equation is a rational number and the right side is irrational, which produces a contradiction. Therefore the assumption is false.
Q.E.D.
Is it possible in three dimensions? Yes, easily. Any triangle with vertices (a,0,0), (0,a,0) and (0,0,a) where a is any non-zero number will work. So just choose any integer value other than 0 for a and you will have an equilateral triangle where each side is .
5. Given: a and b are relatively prime integers. Let k and l be natural numbers.
Prove: and are relatively prime.
Proof:
Suppose for the sake of contradiction that and are not relatively prime.
Thenthe greatest common factor of is cfor some natural numbercgreater than 1.
Nowcgreater than 1 implies chas some prime factor p.
Therefore p must be a factor of both and .
But p a factor of implies p must be a factor of a; and p a factor of implies p is a factor ofb.
Thus p is a factor of a andb.
Thus a and b are not relatively prime.
But this contradicts the given.
Therefore and must be relatively prime.
6. (111,111,111)2 = 12345678987654321 or (1,111,111,111)2 = 1234567900987654321
7. a) Partition S into 15 sets: {1,2}, {3,4}, ..., {29,30}. Note that each set contains two relatively prime integers.
If we select 16 different integers from S, then by the Pigeon Hole Principle two of those integers must come from the same set. Those two integers are relatively prime.
b) Partition S into 15 sets: {1,2,4,8,16}, {3,6,12,24}, {5,10,20}, {7,14,28}, {9,18}, {11,22},
{13,26}, {15,30}, {17}, {19}, {21}, {23}, {25}, {27},{29}.
Note that for any of these sets containing two integers or more, the lower of any two integers in that set is a factor of the higher integer.
If we select 16 different integers from S, then by the Pigeon Hole Principle two of those integers must come from the same set. That means for those two integers, the lower will be a factor of the higher.
Q.E.D.