5
$\begingroup$

How many ways are there to color $1\times1$ squares in a $4\times5$ rectangle with four colors in a way that every $2\times2$ square contains all four colors?

The answer to this is very simple but needs to prove sth that I can't. The following statement:

In every coloring we use two colors repeatedly in a column or row I mean like below here is the column case:

enter image description here

Any hints?

$\endgroup$
  • $\begingroup$ It's important to note that, for instance, the colors in the 4th column there could be (from top to bottom) blue/green/blue/green instead of green/blue/green/blue and it would still be a correct solution. $\endgroup$ – Steven Stadnicki Aug 18 '17 at 18:11
  • $\begingroup$ @StevenStadnicki Yes I know.I mean every column $or$ row. $\endgroup$ – Taha Akbari Aug 18 '17 at 18:13
  • $\begingroup$ In the first column you could use all four colors; you don't need two alternating. $\endgroup$ – Michael Hardy Aug 18 '17 at 18:24
  • $\begingroup$ @MichaelHardy Yes But then you have to use only two colors in every column and I don't know why. $\endgroup$ – Taha Akbari Aug 18 '17 at 18:29
  • 1
    $\begingroup$ Here is a tip: Start by colouring one of the two central $2\times 2$ squares with colours A,B,C and D $$\begin{array}{|c|c|}\hline A&B\\\hline C&D\\\hline\end{array}$$ then use deduction to manually find the number of ways you can fill in the rest of the $4\times 5$ rectangle. Turns out there are only $11$ configurations, and since the $4$ colours can be interchanged in $4!$ ways there are $11\cdot 4! = 264$ colourings with those restrictions. $\endgroup$ – N. Shales Aug 19 '17 at 3:37
2
$\begingroup$

WRONG ANSWER BELOW

Clearly, there are $4! = 24$ ways in a $2\times 2$ rectangle.

Now add one column to the right, making it a $2 \times 3$ rectangle. We already colored the $2 \times 2$ square in the left of this $2 \times 3$ rectangle (in $24$ ways), but the remaining two boxes are not colored yet. This two new boxes can be colored in $2 \cdot 1 =2$ ways.

Therefore, a $2 \times 3$ rectangle can be colored in $24 \cdot 2 = 48$ ways.

Similarly, adding one more column to the right will give two extra boxes, and there will be $48 \cdot 2=96$ ways to color a $2 \times 4$ rectangle.

Finally, adding one more column to the right, we will have $96\cdot 2 = 192$ ways to color a $2 \times 5$ rectangle.

Now we start adding rows.

Observe that, after adding one row to a $2 \times 5$ rectangle, although we will have $5$ new uncolored boxes, when the uncolored box on the very left is colored, the color of the remaining boxes are determined.

Since the box on the very left can be colored in two colors, there are $192 \cdot 2 = 384$ ways to color a $3\times 5$ rectangle.

Finally, we add one more row, and there are $384 \cdot 2 = 768$ ways.

EDIT: Apparently, I cannot delete my answer if it is accepted. As the comments below suggested, there are some cases where this method fails to create a $4 \times 5$ rectangle.

$\endgroup$
  • $\begingroup$ This answer is simply wrong, the reason being that you cannot always complete the third and the fourth row in a legal way. An example: $$\matrix{0&a&b&c&b \cr b&c&0&a&0\cr a&0&&&\cr}$$ $\endgroup$ – Christian Blatter Aug 19 '17 at 8:27
  • $\begingroup$ @ChristianBlatter you are right. I am deleting my answer $\endgroup$ – ThePortakal Aug 19 '17 at 8:29
5
$\begingroup$

Let's consider separately cases where there are $4,2$ and $3$ different colours in the first column.

Case 1:

$4$ different colors. This has only one pattern since the outermost colors must switch places with the center two colors and there is only one way this can happen. Colors can be chosen in $4!=24$ different ways. $$\begin{bmatrix}a&c&a&c&a\\b&d&b&d&b\\c&a&c&a&c\\d&b&d&b&d\end{bmatrix}$$

Case 2:

$2$ different colors. First column can be constructed in $4\cdot3=12$ ways. There can only be $2$ colors per column, but for every column from $2$ to $5$ there are two possible arrangements. In total there are $12\cdot2^4=192$ solutions.

$$\begin{bmatrix}a&c&a&c&a\\b&d&b&d&b\\a&c&a&c&a\\b&d&b&d&b\end{bmatrix}$$

Case 3:

3 different colors.

I) The first column can not be of the form $$\begin{bmatrix}a\\b\\c\\a \end{bmatrix}$$ (this would imply the two center colors would both be $d$)

II) If the same colors are arranged as follows there is only one pattern (since third row is fixed):

$$\begin{bmatrix}a&d&a&d&a\\b&c&b&c&b\\a&d&a&d&a\\c&b&c&b&c\end{bmatrix}$$

The colors can be chosen in $4\cdot3\cdot2=24$ ways.

III) The last possibility is case II) flipped. $24$ more combinations.

So in total there are $$24+192+2\cdot 24=264$$ ways color the squares such that the conditions are fulfilled.

$\endgroup$
1
$\begingroup$

Identify the four colors with the elements $0$, $a$, $b$, $c$ of the Klein four-group, having addition table $$a+a=b+b=c+c=0,\quad a+b=c, \ b+c=a, \ c+a=b\ .$$ An admissible $4$-coloring of the square tiles then induces a coloring of the interior edges with the colors $a$, $b$, $c$ as follows: Color each such edge with the difference of the colors on the adjacent faces. Consider an interior vertex $v$. It is easy to check that the four faces meeting at $v$ show all four colors iff the two vertical edges ending at $v$ get the same color, say $a$, and the two horizontal edges ending at $v$ get the same color, but $\ne a$, as well. It follows that each horizontal and each vertical dividing line in the picture is colored with a single color.

We can color the three horizontal dividing lines with two colors in $3\cdot(2^3-2)=18$ ways, and then all vertical lines have to be colored with the third color. Similarly, we can color the four vertical dividing lines with two colors in $3\cdot(2^4-2)=42$ ways, and then all horizontal lines have to be colored with the third color. Finally we can color all horizontal lines the same way and all vertical lines the same way in $6$ ways. It follows that there are $66$ admissible colorings of the interior edges in the picture.

Conversely: Since each such coloring of the edges sums to $0$ at all vertices $v$ it determines a coloring of the square tiles "up to an additive constant". It follows that there are $4\cdot66=264$ admissible colorings of the tiles in the picture.

$\endgroup$
0
$\begingroup$

First, prove that every valid coloring satisfies one or both of the below conditions:

  1. Every row contains only two colors.
  2. Every column contains only two colors.

To prove this, suppose that some row contains three colors. Then it must contain three adjacent cells which are all different colors. Show that these three cells uniquely determine the three cells above and below, and so on until those three columns are determined. You will see that these three columns must each have only two colors, which then forces all other columns to only have two colors.

Once you've proven the lemma, count the total number of colorings using $|A\cup B|=|A|+|B|-|A\cap B|$.

$\endgroup$
0
$\begingroup$

Denote the colors by $1,2,3,4$.

There are $4!$ ways to color the upper left $2\times2$ square, so assume WLOG that it is colored $1\;2$

$\hspace{5.68 in}3\;4$.

1) If the lower left $2\times2$ square is colored the same way, then there are 2 ways to color each of the remaining columns, giving $2\cdot2\cdot2=8$ possibilities.

2) If the lower $2\times2$ square is colored either $1\;2\;$ or $\;2\;1\;$ or $\;2\;1$

$\hspace{2.82 in}4\;3\hspace{.327 in}3\;4\hspace{.3 in}4\;3,$

then there is only one way to complete each of the remaining 3 columns.

Therefore there are $4!(8+3)=24(11)=\color{blue}{264}$ possible colorings.

$\endgroup$

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.