2
$\begingroup$

The vertices $A,B,C,D$ of a square $ABCD$ are to be coloured with one of three colours red, blue, or green such that adjacent vertices get different colours. What is the number of such colourings?

It seem that if $A$ is red coloured then none of $B$ or $D$ can be coloured by red one, so there are two options blue or green.Then if one of $B$ or $D$ is coloured with blue then $C$ can't be coloured with blue (same as for green one). Then we can colour $A$ by 3 ways (I mean we can colour $A$ by one of three colours) then $B$ by 2 ways again $C$ by two ways and lastly $D$ by also $2$ ways. So the nunber of such colourings must be $3×2×2×2=24$ ways. Is my way of approach is correct and also my answer? Please help me to solve this. Thanking you.

$\endgroup$
1
$\begingroup$

Without loss of generality, let $A$ be red. Then $B$ and $D$ can be independently coloured blue or green. If they are different (two ways), $C$ must be red. If they are the same (two ways), $C$ can be either red or the colour that $B$ and $D$ are not.

Similar reasoning applies if $A$ is blue or green. Thus there are $3(2\cdot1+2\cdot2)=18$ ways, not 24 as you calculated.

A generalised problem, counting the colourings of a square with $n$ colours, is given by OEIS A091940.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If we use only two of the three colours then $(A,B,C,D)=(X,Y,X,Y)$ where $X$ can be chosen in $3$ ways and $Y$ in $2$ ways. So the number of such colourings is $3\cdot 2=6$.

If we use all three colours then $(A,B,C,D)=(X,Y,X,Z)$ or $(A,B,C,D)=(Y,X,Z,X)$ where $X$ can be chosen in $3$ ways and $Y$ in $2$ ways and $Z$ in $1$ way. So the number of such colourings is $2\cdot (3\cdot 2\cdot 1)=12$.

Hence the total number of colourings is $6+12=18$ (not $24$).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let ${\mathbb Z}_3$ be the set of colors. There are six ways of assigning $\pm1$ to the edges of the square such that the sum is $=0$ mod $3$, namely four of cyclic type $(1,1,-1,-1)$ and two of type $(1,-1,1,-1)$. Given such an assignment $s$ there are three colorings $f$ of the vertices such that (in the obvious interpretation) $\partial f= s$. It follows that there are $18$ admissible colorings in all.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.