The squares of a $3\times3$ board can each be coloured using either of 3 possible colours. In how many ways can the 9 squares be coloured such that no two adjacent squares have the same colour? Two squares are adjacent if they share a common edge.

The above links and their content are not associated with the Climb Foundation unless otherwise specified. They are provided as is.

  1. How many 3-digit numbers can be formed from the digits $2, 3, 5, 6, 7$ and $9,$ which are divisible by $5$ and none of the digits is repeated?
  2. How many ways can you arrange 3 boys and 3 girls in a row such that no two boys or two girls are sitting next to each other?

Why not first colour one square and calculate how many ways to choose the colours for the remaining 8 squares?

Which square would be the most convenient one to colour first?

Let A be the colour used for the centre square. For the remaining 8 squares, which ones cannot be coloured with A? Which ones can?

With that in mind, how about calculating the number of ways to colour the 8 squares?

… by considering different cases on the number of squares coloured with A.

Remember that we can colour the first square with any of the three possible colours.

Let’s name the colours A, B, and C. We will assume that A is in the centre and calculate how many ways there are to choose colours for the remaining 8 squares. After that, we get the final answer by multiplying the value by 3.

After colouring the centre square with A, we are left with a cycle of uncoloured squares around the centre. We notice that when we have to colour any path of uncoloured squares with 2 colours, there are only 2 ways to do this (the colour of the first square determines the rest). For a cycle, the same is true provided that it has an even number of squares.

Now with the centre square coloured A, other As can only be in the corners. We consider a few cases:

  • No additional As gives us $2$ ways of colouring one even cycle.
  • One A in one corner breaks the cycle into one path, which gives us ${4\choose1}\cdot2 = 8$ ways.
  • Two As divide the cycle into two paths, which gives us ${4\choose2}\cdot2\cdot2= 24$ ways.
  • Three As divide the cycle into three paths, which gives us ${4\choose3}\cdot2\cdot2\cdot2= 32$ ways.
  • Four As divide the cycle into four paths, which gives us $2\cdot2\cdot2\cdot2 = 16$ ways.

Our final answer is $3\cdot(2+8+24+32+16) = 246.$

The content on this page is best viewed on a display wider than that of a phone, to avoid clipping long math expressions. If any math content looks wrong then please try another browser (e.g. Brave).