Assignment 3 A Colouring Puzzle Due on Friday, 2 February 1. Suppose that finite
ID: 2257579 • Letter: A
Question
Assignment 3 A Colouring Puzzle Due on Friday, 2 February 1. Suppose that finitely many, possibly overlapping, circles are drawn in the plane, dividing it into regions whose borders are made up of circular arcs. Explain how the regions can be coloured using white and black so that no two regions sharing a common border have the same colour, and explain why your method works. [9) NoTE. Just in case: regions touching at only finitely many points do not share a border. 2. Draw a picture explaining why this could be a Mickey Mourse problem. [1)Explanation / Answer
ANSWER:
From the induction on the number of circles. For each natural number n, let Claim(n) be: ‘The regions created in the plane by n circles can be coloured with two colours’.
Step 1: It is clear that the regions created by a single circle can be coloured with two colours, as there are only two regions.
Step 2: Let k be a natural number, and assume that Claim(k) is true, i.e., assume that the regions created in the plane by k circles can be coloured with two colours.
We wish to use this to show Claim(k +1), i.e., that the regions created in the plane by k+1 circles can be coloured with two colours. Assume that we have k + 1 distinct circles in the plane. Choose any one of them, say l, and remove it. We are left with k circles, and so the resulting regions can be coloured with two colours, as we have assumed that Claim(k) is true.
Hence, there is a two-colouring of this set of regions. Take such a colouring of the regions, say with black and white, and add the circle l back. Change the colour of each region on one side of the circle (so black becomes white and white becomes black) and go away the regions on the other side of their original colour. Consider two regions that share a border. There are two cases: either the border is part of the circle l or it is not. By the principle of mathematical induction, it follows that, for every natural number n, the regions created in the plane by n circles can be coloured with two colours.