Question

The plane is divided into a finite number of regions by drawing infinite straight lines in an arbitrary manner. Show that these regions can be 2-coloured.

Short answer

Yes, any plane divided into a finite number of regions by drawing infinite straight lines in an arbitrary manner can be 2-coloured. This was proven by mathematical induction.

Step-by-step solution

Understanding the Base Case

The simplest case of a plane divided by straight lines is where there are not any lines (0 line). So, there's just one region, which can obviously be coloured with one colour. Therefore, our base case is valid.

Inductive Hypothesis

For the inductive hypothesis, let's assume that the statement is true for a plane divided into 'n' regions by 'n' lines, and this plane can be 2-coloured.

Inductive Step

Now, let's prove that even if a new line is added, the resulting plane with 'n+1' lines and corresponding regions can still be 2-coloured. Every time a new line is drawn, it intersects all previously drawn lines. This means it divides existing regions into two, each on either side of the line. These new regions that are formed are adjacent to each other. However, they are not adjacent to the same old regions. Thus, if we change the colour of the regions on one side of the line, a valid 2-colouring can still be maintained.

Conclusion

Since the base case is true and the inductive step has been proven, by mathematical induction, any plane divided by straight lines can be 2-coloured.

Key concepts

Mathematical Induction

Mathematical induction is a powerful proof technique used in mathematics to establish the truth of an infinite number of cases by demonstrating it for one initial case (the base case) and then proving that if it holds for an arbitrary case, it must also hold for the next case (the inductive step).

It operates on the principle that if both the base case is true, and the inductive step is true, then the statement must be true for all natural numbers. The logic resembles a row of dominoes falling – once the first one (the base case) is knocked over, and you ensure each subsequent domino (the inductive step) will fall when hit by its predecessor, you can conclude that all the dominos will fall. In the context of plane division by straight lines, we start with the simplest scenario, a single region, and then prove that adding any number of lines, thus increasing regions, will always allow for a 2-colouring scheme that we can confidently extend to an arbitrary number of lines and regions.

Plane Division with Straight Lines

The concept of dividing a plane into different regions using straight lines is an intriguing problem in graph theory, which has applications in areas such as cartography and network design. Each time a line is drawn on a plane, it intersects with other lines, creating new regions. These regions are essentially polygons, and the task of 2-colouring becomes interesting when considering the common borders.

To visualize this, imagine you're drawing non-intersecting lines on a flat surface, like doodling on a piece of paper. Every new line you draw creates additional spaces. Now, when we have a finite number of lines, and consequently, a finite number of regions, we can engage in colouring these regions. The goal of 2-colouring is to assign one of two colours to each region in such a way that no two adjacent regions (those sharing a common boundary) have the same colour. The rules resemble those of a simple map colouring challenge, ensuring that each 'country' (or region) is distinct from its neighbours.

Graph Colouring

Graph colouring is a method of assigning colours to the vertices, edges, or regions of a graph in a way that no two adjacent elements share the same colour. The focus on 2-colouring within a plane divided by straight lines falls within the area of vertex and region colouring – where we colour regions created by the intersections of the lines such that no two adjacent regions share the same colour.

The significance of graph colouring transcends beyond theoretical puzzles and has practical applications in scheduling problems, electronic map colouring, and solving Sudoku puzzles. In the problem at hand, a successful 2-colouring design indicates that the regions can be colour-coded without conflicts, which implies a practical way of demonstrating the concept of plane division without ambiguity concerning adjacent regions. It's a visual and intuitive approach to ensure distinct identities within a shared space, providing visual clarity and functional organization.