So I have the following task:
We have a rectangle $2 \times 4$ cells and four colors: red, green, blue, black.
How many ways are there to paint each cell, so that no two
cells with a common side were painted the same color.
How to solve this? I'm interested in the explanation first and some pattern for such tasks cause my teacher didn't explain me.
Best Answer
Hint: If we think rotated rectangles are different: so
Red Green Blue Black
Black Blue Red Green
is different from
Green Red Blue Black
Black blue Green Red
There are 12 choices for the first column. How many choices are there for the second column? For the third?
If you worry about rotations, it becomes harder. You might also count rectangles that can be made to match by reassigning colors the same. Then you can arbitrarily start with Red Green in the first column, but it is also hard.
Added in response to comment: in the case where you count rotations as the same, we have double counted all the rectangles except the symmetric ones, so we just need to count those. The last half of the columns are specified when you pick the first half. So again you have 12 choices for the first column and 7 for the second. As dtldarek pointed out, you can always invert the second column to make the third and the first to get the fourth. So there are 84 symmetric cases. The total with rotations the same is then $(12\cdot7^3-84)/2+84=2100$.