Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
1.8k views
in Olympiad by (76.3k points)

Consider n2 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 ?

1 Answer

+1 vote
by (65.8k points)
selected by
 
Best answer

as per given condition, (i, k), (j, k), (j, l) are of distinct colour. No two square of kth 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.

by (10 points)
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

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...