Question: Question 2: Consider a rectangular grid of points with 5 rows and 41 columns. Each point is assigned a colour from the set {black, red,

Question 2: Consider a rectangular grid of points with 5 rows and 41 columns. Each point is assigned a colour from the set \{black, red, blue, green . We will prove that, regardless of how it is coloured, we can find 4 points the same colour that form the corners of a rectangle. The example below shows one such rectangle formed on green points. a) First prove that in each column there is at least one colour that appears twice. b) Give each column a label that corresponds to a colour that appears at least twice in that column. For instance, the first column in the example below should be labelled green. Prove that there is at least one colour that appears at least 11 times in the column labels. c) Let C be the colour that appears at least 11 times in our column labels. Prove that, among these 11 or more columns, that there exists two columns containing two points coloured C at the same y-coordinates. These four points form a rectangle, which completes the proof
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
