Hey I'm having some troubles solving this problem:

Consider a rectangle R. Start drawing n line segments L1, L2, …, Ln such that each line segment has both endpoints on the boundary of the rectangle. Notice that this partitions the rectangle R into a bunch of regions. Suppose you have two colors, black and white. Prove by induction that you can always find a way to paint each of the regions with either black or white such that every two regions that share a piece of segment (not a point) gets a different color. In other words, two regions that share a piece of segment never get coloured with the same color.

Thanks

klbcooldude

Any ideas?

s_cianci

"Proof by induction", as you say, means that you first prove it for an initial condition. Then, assume that it's true for some arbitrary number of iterations, n. With that assumption, show that it's true for n + 1 iterations. In this case, your initial condition would be n = 2, i.e. you draw 1 line segment, thus dividing the rectangle into 2 regions sharing your line segment as a boundary. You then simply color 1 region white and the other black. Then, with that proven, show that if it's true for any number of regions n, it has to be true for n + 1 regions.