If have to find The number of different ways to colour the vertices of a square PQRS using one or more colours from the set {R,G,B,Y}, such that no two adjacent vertices have the same colour is?
So starting from the vertex on the top left (say P), there are 4 possible colours, as Q can't be identical to P, Q can be coloured any of 3 colours, as can R , and S too. .
thus the answer must be $4*3^3 =108$.
however, I know this is wrong.
What am I doing wrong?
Best Answer
What you did wrong:
Q can't be identical to P is correct but R can be identical since it is not adjacent to P
P,R can be identical Q,S can be identical
Solution:
Case-I P,R are identical
->P can take any of the four colors but R doesn't have a choice since it has to take what P takes to be identical ->Q on the other hand can take 3 colors and so can R
So, 4.3.1.3 ( S either takes what Q takes or the any one of two remaining)
Case- II P,R are different
-> 4.3.2.2 here S has two choices ( either take what q takes or take the remaining color) Total no. of ways = 84