klbcooldude
Oct 31, 2009, 11:52 PM
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
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