3
$\begingroup$

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.

  • 1
    You may also see this one: http://math.stackexchange.com/questions/112565/coloring-a-4-times-4-square-with-4-colors , which is a harder problem!2012-05-14

3 Answers 3

3

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$.

  • 0
    @dtldarek: right you are. I will incorporate it into the answer. I was afraid of conflicts between the second and third column, but they cannot happen. Thanks.2012-05-14
2

Hint:

In the following I assume that the rectangle has 4 columns and 2 rows.

  1. In how many ways you can set up first two squares (first column)? Let's call this number $\alpha_1$.
  2. In how many ways you can pick colors for next two squares? Let's call this number $\alpha_2$.
  3. Does the colors in the third column depend on the first column? Does the colors in $i$-th column depend on the $(i-2)$ column? Can you show that $\alpha_4 = \alpha_3 = \alpha_2$?
  4. Finally, the answer will be $\alpha_1\cdot\alpha_2\cdot\alpha_3\cdot\alpha_4$, in you case this is $12\cdot7\cdot7\cdot7$.
  • 1
    @JohnGray Simple enumeration, if you set $i$-th column, then you have $4-1$ options for first rectangle of the $(i+1)$-th column (it has one neighbor set already) and $4-2$ options for the second (two neighbors set already) and there is one special case where the two neighbors use the same color, and that totales to $3\cdot 2 + 1 = 7$ cases. On the other hand it is easy enough to draw them all: if you start with `12` in the $i$-th column, then you have the following choices for the $(i+1)$-th: `23`, `24`, `31`, `34`, `41`, `43`, and `21`.2012-05-18
0

Let say

${}_4P_2 \times ({}_4P_2- 2 -2 -1 ) \times ({}_4P_2 - 2 -2 -1 )\times({}_4P_2 - 2 -2 -1) = 12 \times 7 \times 7 \times 7 $ where ${}_nP_{k} = \frac{n!}{(n-k)!}$ is the number of ways of obtaining an ordered subset of $k$ elements from a set of $n$ elements.

  • 4
    Care to elaborate a bit on how you arrived at that answer?2012-05-16