UPSC PYQPrelims 2011

Civil Services Examination · Question 37

Consider the following figure and answer the item that follows: What is the minimum number of different colours required to paint the figure given above such that no two adjacent regions have the same colour?

Figure given in the question
  1. 3

  2. 4

  3. 5

  4. 6

Show answer & explanationShow explanation

Answer: (A) 3

Explanation

Given / Concept: Two regions sharing a boundary must have different colours; if three regions mutually touch one another, at least 3 colours are required. Lower Bound = 3: In the 6-sector ring (Ring 3), any two adjacent sectors touch each other and also touch the undivided ring (Ring 2) ⇒ at least 3 colours are necessary. Construct 3-Colouring: Paint the center disk with Colour 1, undivided Ring 2 with Colour 3, the 6 sectors of Ring 3 alternately with Colours 1 & 2 (since 6 is even), undivided Ring 4 with Colour 3, and the 8 outer sectors of Ring 5 alternately with Colours 1 & 2 (since 8 is even). Result: The minimum number of different colours required is 3. Correct Answer: (a) 3

Diagram explaining the answer