Question

Consider n² unit squares in the xy-plane centred at point (i, j) with integer coordinates, 1 ≤ i ≤ n, 1 ≤ j ≤ n. It is required to colour each unit square in such a way that when ever 1 ≤ i < j ≤ n and 1 ≤ k < l ≤ n, the three squares with centres at (i, k), (j,k), (j, l) have distinct colours. What is the least possible number of colours needed ?

Answer 1

as per given condition, (i, k), (j, k), (j, l) are of distinct colour. No two square of k^th row will be of same colour as (i, k) and (j, k) are of distinct colour and no two squares of ith column of same colour as (j, l) and (j, k) are of distinct colour. 

⇒ all squares of type (x, 1) for x = 1, 2, 3, … n are of distinct colour ⇒ total n distinct colours. 

Similarly all square of type (n, y) for y = 1, 2, …. n are of distinct colour, also no squares of (x, 1) & (n, y) with same colour otherwise take square (n, n) with (x, 1) and (n, y); we get contradiction to given condition.

 There will be atleast 2n – 1 colours. Now let us prove 2n – 1 colours are sufficient 

 

We can see that (x, y) & (x + 1, y – 1) can have same colours. So paint all squares with same colours for which x + y is same.  

Here minimum x + y will be 2(for x = 1, y = 1) & maximum x + y = 2n 

 As from 2 to 2n there 2n – 1 values, So 2n – 1 colours will be sufficient.

Comments

let first row is colored with n different colours say c1 c2 ... cn . Second row i colored with same colours with different positioning , that is , c2 c3 c4 ... cn and in last sqaure c1 . Third row again with same colours with different arrangment , c3 c4 c5 ... cn c1 c2 . And so on ..... so n different colours are needed . What is the problem in following solution . Thank you for any help