Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So i have the following task:

We have a rectangle 2 by 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 =(

share|improve this question
1  
You may also see this one: math.stackexchange.com/questions/112565/… , which is a harder problem! –  Goodarz Mehr May 14 '12 at 15:25

4 Answers 4

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

share|improve this answer
    
So the only way to solve this is to draw each variant on the paper and count ways by hand? –  4lex1v May 14 '12 at 14:01
    
That's not a good idea. There are 4^(2*4)=65536 possible ways of coloring. –  miloszmaki May 14 '12 at 14:03
    
@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. –  Ross Millikan May 14 '12 at 14:08
    
OK, so I've coded a simple program and the result turns out to be 4116 out of 65536 possible ways. –  miloszmaki May 14 '12 at 14: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$ –  Ross Millikan May 14 '12 at 14:17

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$.
share|improve this answer
    
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. –  Tomarinator May 14 '12 at 14:34
    
@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. –  Ronald May 14 '12 at 14:37
    
Can we move this discussion over to another answer to facilitate communication, as referring to cells can be confusing without a picture. –  Tomarinator May 14 '12 at 14:40
    
Sor for he late response, but how did't you get 7 for columns 2..4? –  4lex1v May 18 '12 at 16:49
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. –  dtldarek May 18 '12 at 17:34

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.

share|improve this answer
3  
Care to elaborate a bit on how you arrived at that answer? –  Willie Wong May 16 '12 at 11:09

4p2 4p2-2-2 4p2-2-2-1 4p2-2-2-1=12+7+7+7

share|improve this answer
9  
Can you explain your answer a little better? –  Jonathan Christensen Dec 14 '12 at 3:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.