A Modest Attempt at the "Cross" Combinatorics Problem

“十字架”组合计数问题浅试 苏剑林 · 2022-10-09 · Mathematics proof mathematics combinatorics

Yesterday I came across this WeChat article, which discusses a "cross" combinatorics problem whose answer is apparently disputed:

In a square, if two of the four sides are colored $i$ and the other two are each a different color, the square is said to be "$i$-dominated." Consider the "cross" figure below, made up of 16 line segments forming 5 squares. Each segment is colored one of red, yellow, or blue, such that the three horizontal squares and the three vertical squares each have mutually different dominant colors. How many distinct colorings are there?
Illustration of the "cross"

The linked article gives two different answers: 54432 from Mr. Wu Kang, and 27216 from Mr. Wang Huixing. In this post I'll first confirm programmatically that Mr. Wang's 27216 is correct, and then walk through my own theoretical derivation.

Programmatic verification

For a counting problem with numbers this small, the most direct way to check the answer is brute-force enumeration. The most straightforward approach would be to enumerate all possible colorings of the 16 segments and then check each one against the constraints. However, this requires enumerating $3^{16}\approx 4300\text{ten thousand}$ possibilities, which is quite a lot of computation, so it's worth finding a way to cut this down.

First, it's natural to label the five squares "top," "bottom," "left," "right," and "center," as shown below:

Natural partition labeling of the "cross"

Clearly, among these five squares, "center" plays a special role, so whether doing the theoretical analysis or the programmatic computation, we start from it. For coding convenience, let's map the colors red, yellow, and blue to the numbers 0, 1, 2 respectively. We can then quickly enumerate all possible colorings of "center":

from itertools import product

centers = [s for s in product(*[range(3)] * 4) if len(set(s)) == 3]

Next, for each coloring scheme of "center," we enumerate the corresponding coloring schemes of "top," "bottom," "left," and "right." The method is simple: first identify the dominant color of the "center" coloring, then let the dominant colors of "top-bottom" and "left-right" each be chosen from the remaining two colors, and multiply together the numbers of coloring schemes for "top," "bottom," "left," and "right." Note that once the "center" coloring is fixed, when enumerating the "top," "bottom," "left," "right" schemes, each of them already has one side whose color is fixed, so the number of options to enumerate should be $3^3$ rather than $3^4$. The full reference code is as follows:

def master(s):
    """识别主导色
    """
    for i in range(3):
        if s.count(i) == 2:
            return i

N = 0
for c in centers:
    m = master(c)  # 当前主导色
    M = [i for i in range(3) if i != m]  # 剩余两种颜色
    for i in range(2):  # 上、下主导色
        for j in range(2):  # 左、右主导色
            top = [s for s in product([c[0]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[i]]
            bottom = [s for s in product([c[2]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[1 - i]]
            left = [s for s in product([c[1]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[j]]
            right = [s for s in product([c[3]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[1 - j]]
            N += len(top) * len(bottom) * len(left) * len(right)

print(u'总染色方案数为', N)

This gives a final total of 27216 coloring schemes.

Theoretical calculation

Theoretically, the idea is the same as the experimental verification: start from the center, then work outward to the two pairs of side squares — except that the brute-force enumeration part in the code is replaced by combinatorial formulas.

First, let's count the coloring schemes for "center" again. Looking at the combinations, there are three types: "0 0 1 2," "0 1 1 2," and "0 1 2 2." Take "0 0 1 2" as an example: inserting a 1 into "0 0" gives 3 possible positions, and then inserting a 2 gives 4 possible positions, so each combination yields $3\times 4=12$ arrangements. Hence the total number of coloring schemes for "center" is $12\times 3 = 36$.

Next, we split the "center" coloring schemes into two categories, as shown below: (1) the two dominant colors are adjacent; (2) the two dominant colors are opposite.

"Center" scheme 1: dominant colors adjacent"Center" scheme 2: dominant colors opposite

Clearly the ratio between the two categories is 2:1, so among the coloring schemes of "center," 24 have adjacent dominant colors and 12 have opposite dominant colors. Let's analyze these two cases separately.

Case 1: dominant colors adjacent. Without loss of generality, consider the case shown in the left figure above, where the dominant color of "center" is red. Then the dominant colors of "top" and "bottom" can only be chosen from yellow or blue. Suppose "top" has dominant color yellow — then it has only 3 possible colorings, and correspondingly "bottom" also has only 3 possible colorings, so "top-bottom" together has $3\times 3=9$ coloring schemes. If instead "top" has dominant color blue, it again has only 3 possible colorings, but correspondingly "bottom" has 6 possible colorings, giving $3\times 6=18$ schemes for "top-bottom." Adding the two cases together gives $9+18=27$ schemes. The analysis for "left-right" is identical, and "top-bottom" and "left-right" can be combined freely, so together there are $27\times 27=729$ schemes. Note that this is only for one particular coloring scheme of "center," so the total number of colorings in this case is $729\times 24=17496$.

Case 2: dominant colors opposite. Without loss of generality, consider the case shown in the right figure above, where the dominant color of "center" is red. Then the dominant colors of "top" and "bottom" can only be chosen from yellow or blue. Suppose "top" has dominant color yellow — then it has only 3 possible colorings, and correspondingly "bottom" also has only 3 possible colorings, so "top-bottom" together has $3\times 3=9$ coloring schemes. If instead "top" has dominant color blue, it again has only 3 possible colorings, and "bottom" likewise has only 3 possible colorings, giving $3\times 3=9$ schemes for "top-bottom." Adding the two cases together gives $9+9=18$ schemes.

But in this case, the result for "left-right" is different from "top-bottom," and needs to be analyzed separately. Suppose "left" has dominant color yellow — then it has only 3 possible colorings, and correspondingly "right" also has only 3 possible colorings, so "left-right" together has $3\times 3=9$ coloring schemes. If instead "left" has dominant color blue, it has 6 possible colorings, and "right" likewise has 6 possible colorings, giving $6\times 6=36$ schemes for "left-right." Adding the two cases together gives $9+36=45$ schemes. So the total number of colorings for "top," "bottom," "left," "right," "center" together in this case is $18\times 45\times 12=9720$.

Finally, adding the two cases together gives $17496+9720=27216$ total colorings.

Summary

It's been a while since I did a math problem — just a bit of a refresher on high-school math!