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
    So the only way to solve this is to draw each variant on the paper and count ways by hand?2012-05-14
  • 0
    That's not a good idea. There are 4^(2*4)=65536 possible ways of coloring.2012-05-14
  • 0
    @miloszmaki: It's much easier than it looks. When doing by hand you can force the first column to be what you like and multiply by 12 at the end. You can also quit as soon as it fails, like if the top second column matches the top first. That said, there are still many possibilities. A backtracking computer program would make quick work of it.2012-05-14
  • 0
    OK, so I've coded a simple program and the result turns out to be 4116 out of 65536 possible ways.2012-05-14
  • 0
    @miloszmaki can your share your code2012-05-14
  • 1
    @miloszmaki: $4116$ is correct if you count rotations as different. Then you can follow my original hint and do it easily by hand. With rotations the same it should be about half that plus about $12*7/2=42$ or close to $2100$2012-05-14
  • 0
    @John Gray: http://pastebin.com/DC9nY5dV2012-05-14
  • 0
    @RossMillikan There are 84 colorings that are the same under rotation, so there are $(4116-84)/2+84=2100$ different colorings in that case.2012-05-14
  • 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$.
  • 0
    shouldnt $\alpha_2$ be 6 instead of 7? because we got 3 choices for first row and 2 for 2nd row in the 2nd column.2012-05-14
  • 0
    @SauravTomar Your method here is wrong, because the diagonal squares can be the same. And, when they are the same, we'll have 3 choices for 2nd row in the 2nd column.2012-05-14
  • 0
    Can we move this discussion over to another answer to facilitate communication, as referring to cells can be confusing without a picture.2012-05-14
  • 0
    Sor for he late response, but how did't you get 7 for columns 2..4?2012-05-18
  • 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