Schematic of the "Cross"
By 苏剑林 | October 09, 2022
Yesterday, I saw a "cross" combinatorial counting problem in a WeChat public account article that is said to have a controversial answer: In a square, if two of the four sides are of color $i$ and the other two are of two different other colors, then the square is called "$i$-color dominant." Consider the following "cross" figure composed of 16 line segments and 5 squares. Each segment is colored with one of three colors: red, yellow, or blue, such that the dominant colors of the three squares in the horizontal and vertical directions are all different. How many different coloring methods are there?
Schematic of the "Cross"
The linked article provides two answers: 54,432 by Teacher Wu Kang and 27,216 by Teacher Wang Huixing. This post first confirms through programming that Teacher Wang Huixing's 27,216 is the correct answer, and then provides my own theoretical analysis process.
For such combinatorial problems with a relatively small number of permutations, the simplest and most direct way to verify the correctness of the answer is, naturally, programming enumeration. The most straightforward programming method is to enumerate all possible coloring schemes for the 16 line segments and then judge them one by one to see if they meet the requirements. However, this scheme requires enumerating $3^{16} \approx 43 \text{ million}$ schemes, which is quite computationally intensive. Therefore, we can think of ways to reduce the computation.
First, we naturally label the five squares as "Top", "Bottom", "Left", "Right", and "Center," as shown below:
Natural partitioning labels of the "Cross"
Obviously, among these five squares, the "Center" has the most special status. Therefore, whether in theoretical analysis or programming calculation, we use it as the starting point. For the sake of programming convenience, we map the three colors Red, Yellow, and Blue to the digits 0, 1, and 2, respectively. Thus, we can quickly enumerate all possible coloring schemes for the "Center" as follows:
from itertools import product
centers = [s for s in product(*[range(3)] * 4) if len(set(s)) == 3]Then, for each coloring scheme of the "Center," we enumerate the corresponding "Top", "Bottom", "Left", and "Right" coloring schemes. The method is also simple: first identify the dominant color of the "Center" coloring, then let the dominant colors for "Top-Bottom" and "Left-Right" be chosen from the remaining two colors respectively. We multiply the number of coloring schemes for "Top", "Bottom", "Left", and "Right" together. Note that once the "Center" coloring scheme is given, when enumerating the "Top", "Bottom", "Left", and "Right" schemes, one of their sides is already fixed, so the number of enumerable schemes should be $3^3$ rather than $3^4$. The complete reference code is as follows:
def master(s):
"""Identify the dominant color"""
for i in range(3):
if s.count(i) == 2:
return i
N = 0
for c in centers:
m = master(c) # Current dominant color
M = [i for i in range(3) if i != m] # Remaining two colors
for i in range(2): # Dominant colors for Top, Bottom
for j in range(2): # Dominant colors for Left, Right
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'Total number of coloring schemes is', N)Finally, the total number of coloring schemes is calculated to be 27,216.
From a theoretical perspective, the logic for calculating the final number of coloring schemes is the same as the experimental verification: center first, then the sides. However, the brute-force enumeration part of the code is replaced by permutations and combinations formulas.
First is the number of coloring schemes for the "Center." Looking at the combinations, there are three types: "0 0 1 2", "0 1 1 2", and "0 1 2 2". Taking "0 0 1 2" as an example, to insert a 1 into "0 0", there are 3 possible positions, and then to insert a 2, there are 4 possible positions. So each combination has $3 \times 4 = 12$ permutations. Therefore, the number of coloring schemes for the "Center" is $12 \times 3 = 36$.
Next, we divide the coloring schemes of the "Center" into the two types shown in the figure below: 1. The two edges of the dominant color are adjacent; 2. The two edges of the dominant color are opposite.
Top: Center Scheme 1 (Adjacent); Bottom: Center Scheme 2 (Opposite)
Clearly, the ratio of the two is 2:1. Thus, among the "Center" coloring schemes, there are 24 where the dominant color edges are adjacent and 12 where they are opposite. We discuss these two cases separately below.
First, the dominant color edges are adjacent. Without loss of generality, let's consider the left figure above. At this time, the dominant color of the "Center" is "Red," so the dominant colors of "Top" and "Bottom" can only be "Yellow" or "Blue." Assume the dominant color of "Top" is chosen as "Yellow." Then there are only 3 coloring schemes for it, and accordingly, there are also only 3 coloring schemes for "Bottom." Thus, there are $3 \times 3 = 9$ coloring schemes for "Top-Bottom." If the dominant color of "Top" is "Blue," then there are also 3 coloring schemes for it, but the corresponding "Bottom" has 6 coloring schemes. Thus, there are $3 \times 6 = 18$ coloring schemes for "Top-Bottom." Adding the two cases together gives $9 + 18 = 27$ schemes. The analysis for "Left-Right" is the same, and "Top-Bottom" and "Left-Right" can be combined arbitrarily. Therefore, there are a total of $27 \times 27 = 729$ schemes. Note that this is for just one "Center" coloring scheme; hence, the total number of coloring schemes in this case is $729 \times 24 = 17,496$.
Second, the dominant color edges are opposite. Without loss of generality, let's consider the right figure above. At this time, the dominant color of the "Center" is "Red," so the dominant colors of "Top" and "Bottom" can only be "Yellow" or "Blue." Assume the dominant color of "Top" is "Yellow," there are 3 coloring schemes for it, and "Bottom" also has 3 coloring schemes. Thus, "Top-Bottom" has $3 \times 3 = 9$ schemes. If the dominant color of "Top" is "Blue," it has 3 coloring schemes, and "Bottom" also has 3 coloring schemes. Thus, "Top-Bottom" has $3 \times 3 = 9$ schemes. Adding them up gives $9 + 9 = 18$ schemes.
However, in this case, the result for "Left-Right" is different from "Top-Bottom" and requires a separate analysis. Assume the dominant color of "Left" is "Yellow," it has 3 coloring schemes, and "Right" also has 3. Thus, "Left-Right" has $3 \times 3 = 9$ schemes. If the dominant color of "Left" is "Blue," it has 6 coloring schemes, and "Right" also has 6. Thus, "Left-Right" has $6 \times 6 = 36$ schemes. Adding them up gives $9 + 36 = 45$ schemes. Therefore, the total number of coloring schemes for "Top", "Bottom", "Left", "Right", and "Center" together is $18 \times 45 \times 12 = 9,720$.
Finally, adding the two cases together gives $17,496 + 9,720 = 27,216$.
It's been a long time since I've done math problems; this was purely to brush up on high school mathematics knowledge~
Reprinting please include this article address: https://kexue.fm/archives/9291
If you think this article is good, you are welcome to Share / Reward this article. The reward is not for profit, but to know how much sincere attention Scientific Space has received from readers. Of course, if you ignore it, it will not affect your reading. Welcome and thank you again!