Week 11 Journal 10 - Problem Solving SimpleCartography

SimpleCartography

Choose your favourite non-negative whole number. Draw that many straight lines on a sheet of paper (well, at least draw the portion of each line that will fit on the sheet of paper). The lines leave the paper divided into regions (a single region if your favourite non-negative whole number is 0). What is the minimum number of colours you need in order to colour each region so that no two regions that share a common line segment boundary have the same colour?

If somebody else drew the straight lines, do you have a procedure that will produce such a colouring of their regions with a minimum number of colours?

1) Understanding the problem

If we draw line segments to divide a piece of paper in to regions. And we would like to color all the regions with no same color next to each other.

ie, to see how many regions by counting the colored boxes, if they are the same color with connected regions, they will become one colored boxes.

We need to find a given number of lines, and find out how many colors do we need in order to color the paper completely.

2) Devising A Plan

Any non negative number can be picked, including 0.

We need to find the minimum regions from all the possibilities. ie. 0 line segment = 1 regions; 1 line segments = 2 regions, 2 line segments = 3 or 4 regions...

we find that same numbers of line segments would possible have different numbers of regions

3) Carrying Out The Plan

After finding out the possible regions for each number of line segments, we find out that the minimum number of regions will be n + 1

which is drawing all line segments parallel to each other, either all vertically or all horizontally.

If this is the case, we only need at most 3 colors to fit the case because each region has at most one other region beside (left and right) and the most left and most right region on the paper only have one region next to it.

4) Looking Back

In order to make the solution always correct, we need to limit the next line segment can only be draw parallel to those already on the paper.

Then the solution at most 3 colors is needed will be always correct.