I have a $2\times3$ grid which is colored with four colours. How many colourings do there exists such that every two adjacent squares have different colours? I don't know how to start.

  • $\begingroup$ Start by trying to solve similar problems for smaller grids and fewer colors. $\endgroup$ – MJD Jan 14 '17 at 18:39
  • $\begingroup$ @MJD What is the basic idea? $\endgroup$ – Problemsolving Jan 14 '17 at 18:45
  • 1
    $\begingroup$ This idea should work but not in general: Top middle cell has 4 choices, neighbors have 3 choices, then take cases for the last two cells. $\endgroup$ – greenturtle3141 Jan 14 '17 at 18:47

Color the grid by columns (top and bottom cells) going from left to right:

You have $4\cdot 3=12$ ways to color the $1$st column. Now given that you've made your choice of colors for the $1$st column, the number of ways to color the $2$nd column will drop down from $12$ to $7$. The same happens for the 3rd column, once you've colored the $2$nd one . So the total number is $$12\cdot 7 \cdot 7=588.$$

  • $\begingroup$ WHy 7? They are 6? $\endgroup$ – Problemsolving Jan 14 '17 at 20:15
  • $\begingroup$ Let A, B,C, D be the four colors. Suppose the $1$st column is (A,B) (A on the top, and B on the bottom). Can you list the possibilities for the $2$nd column? $\endgroup$ – MathChat Jan 14 '17 at 20:23
  • $\begingroup$ Sorry, you have right! $\endgroup$ – Problemsolving Jan 14 '17 at 20:34

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.