Assume we have a rectangle, R through which we can draw any number of lines. The
ID: 1948399 • Letter: A
Question
Assume we have a rectangle, R through which we can draw any number of lines. The ?rst line we draw (we assume any line we draw intersects R) subdivides R into two faces. Any subsequent line we draw will likewise split one or more of the existing faces, and create a new face(s). Any face we intersect is split into exactly two new faces. We say the lines meet at a vertex and that portion of a line between two verticesis an edge. Two faces are adjacent if and only if they share an edge. Now assume we want to colour the faces in R black or white. Prove using induction that it is always possible to colour the faces in R such that no two adjacent faces are coloured the same. Figure 4 below shows such a subdivision and colouring with one and two lines.
Explanation / Answer
To prove by induction, you first show the base case (number of lines 1, trivial). Then assume for n lines and show for n+1. Consider the "first" n lines of the n+1. By the induction hypothesis, the faces in the division of R can be colored black and white with no adjacent faces having the same color. Now, draw the last line, l, number n+1. Keep the colors of all the faces on one side of l and reverse the colors of the faces on the other side. * Between each pair of adjacent faces that are on one of the sides of l, no two have the same color by the induction hypothesis. If they do have the same color, they had to have the same color before we reversed the colors. * Now, consider pairs of adjacent faces on different sides of l. Before l was drawn, they were part of the same face, so had the same color, so now they have opposite colors.