Three-Coloring Problems in Math Competitions: A Systematic Approach | 数学竞赛考点：三色染色问题解题思路精讲

📚 Three-Coloring Problems in Math Competitions: A Systematic Approach | 数学竞赛考点：三色染色问题解题思路精讲

Three-coloring problems are a classic yet challenging topic in mathematical olympiads. They test not only combinatorial insight but also the ability to recognize invariants, construct clever colorings, and derive contradictions from structural constraints. In this article, we will explore the essential techniques for solving three-color problems, illustrated with typical contest examples.

三色染色问题是数学竞赛中经典而富有挑战性的专题。它不仅考查组合数学的洞察力，更考验学生识别不变量、构造巧妙染色方案以及从结构约束中推导矛盾的能力。本文将系统讲解三色问题的核心解题技巧，并结合典型竞赛题目进行精讲。

1. What Is a Three-Coloring Problem? | 什么是三色染色问题？

A three-coloring problem typically asks whether a given set, graph, or geometric configuration can be colored using exactly three colors under certain constraints, or it uses a three-coloring as a tool to prove a combinatorial statement. The three colors are usually denoted A, B, C or Red, Green, Blue.

三色染色问题通常要求判断某个集合、图或几何构型能否在特定约束下用三种颜色染色，或者利用三色染色作为工具来证明某个组合命题。三种颜色通常记为 A、B、C 或红、绿、蓝。

The power of three-color arguments lies in the fact that three colors introduce a richer structure than two colors. With bi-colorings, we often rely on parity; with three colors, modular arithmetic modulo 3 becomes available, enabling more subtle invariants.

三色染色的威力在于，三色比两色拥有更丰富的结构。对于双色染色，我们通常依赖奇偶性；而三色染色则引入了模 3 的算术结构，使得我们能够构造更精巧的不变量。

2. The Core Idea: Invariants and Contradictions | 核心思想：不变量与矛盾

The most common strategy in three-coloring problems is to define a quantity that is invariant (or changes predictably) under the allowed operations, then compare the initial and final configurations to derive a contradiction.

三色染色问题最常见的策略是定义一个在允许操作下保持不变（或按规律变化）的量，然后比较初始状态和最终状态，从而导出矛盾。

For example, assign numerical values to the three colors — say 0, 1, 2 — and track the sum of all values modulo 3, or the product, or the number of color transitions along a path. Such quantities often reveal hidden impossibilities.

例如，将三种颜色分别赋值为 0、1、2，然后追踪所有值之和模 3、乘积、或一条路径上的颜色变化次数。这些量往往能揭示隐藏的不可能性。

A classic invariant for a 1 × n board filled with triominoes is the alternating sum of colors. If each triomino covers one cell of each color, the total sum stays fixed — a powerful constraint.

对于用三连块覆盖 1 × n 棋盘的问题，一个经典不变量是颜色的交错和。如果每个三连块恰好覆盖三种颜色各一格，那么总和保持不变——这是一个强有力的约束。

3. Example 1: Coloring the Corners of a Cube | 例 1：立方体顶点染色

Problem: Is it possible to color each of the 8 vertices of a cube with one of three colors so that every edge connects two vertices of different colors?

问题：能否用三种颜色给立方体的 8 个顶点染色，使得每条边的两个端点颜色不同？

Solution: Suppose such a coloring exists. Consider any face of the cube. It has 4 vertices forming a cycle. With three colors and adjacent vertices distinct, the four vertices of a cycle must alternate between two colors or use three colors in a pattern like A-B-C-A.

解答：假设这样的染色存在。考虑立方体的任意一个面，它有 4 个顶点构成一个环。在三种颜色且相邻顶点不同的条件下，一个四环的顶点颜色要么在两种颜色间交替，要么按 A-B-C-A 的模式使用三种颜色。

Now examine the entire cube. Each vertex has degree 3. Pick a vertex v colored A. Its three neighbors must have colors different from A, so they are colored B or C. By the pigeonhole principle, two of these three neighbors share the same color, say B and B.

现在考察整个立方体。每个顶点的度为 3。选取一个颜色为 A 的顶点 v，它的三个邻居都不能是 A，因此只能是 B 或 C。根据鸽巢原理，这三个邻居中必有两个同色，不妨设为 B 和 B。

Take the face containing v and these two B-neighbors plus the third neighbor. The two B vertices are not adjacent to each other, so no immediate contradiction. However, triangle-free bipartite constraints force the third neighbor to be C. Repeating the argument, a pattern emerges that ultimately requires two adjacent vertices of the same color — a contradiction.

考察包含 v、两个 B 邻居和第三个邻居的面。两个 B 顶点互不相邻，因此不会立刻产生矛盾。然而，由于图是无三角形的二分约束，第三个邻居只能是 C。重复这一论证，最终会产生两个相邻顶点同色的矛盾。

Thus, no such three-coloring of cube vertices exists. This problem illustrates how local constraints propagate globally.

因此，不存在满足条件的立方体顶点三色染色。这个问题展示了局部约束如何全局传播。

4. Example 2: Tiling with Triominoes | 例 2：三连块铺砌问题

Problem: A 2 × n rectangle is to be tiled with L-triominoes (each covering 3 unit squares). Determine for which n this is possible, and prove it using a three-coloring of the board.

问题：一个 2 × n 的矩形需要用 L 形三连块（每个覆盖 3 个单位方格）铺满。确定使得铺砌可行的 n 值，并用三色染色来证明。

Solution: Color the board periodically in a 3-color pattern. Let the three colors repeat cyclically along the columns:

解答：用三种颜色对棋盘进行周期性染色。让三种颜色沿列方向循环重复：

A	B	C	A	B	C	…
C	A	B	C	A	B	…

In this coloring, every L-triomino covers exactly one cell of each color. You can verify this by checking the four orientations of the L-triomino against the grid pattern. Therefore, in any valid tiling, the number of A-cells must equal the number of B-cells and must equal the number of C-cells.

在这种染色中，每个 L 形三连块恰好覆盖三种颜色各一格。你可以通过将 L 三连块的四种朝向逐一与网格图案比对来验证这一点。因此，在任意有效铺砌中，A 色方格数必须等于 B 色方格数，也必须等于 C 色方格数。

Now count the colors on a 2 × n board. For n = 3k, the counts are equal. For n = 3k + 1, the board has 2n = 6k + 2 cells, so the numbers of A, B, C cells cannot be equal — the board cannot be tiled. For n = 3k + 2, again the counts differ.

现在统计 2 × n 棋盘上各颜色的数量。当 n = 3k 时，三种颜色的格数相等。当 n = 3k + 1 时，棋盘有 2n = 6k + 2 个格子，因此三种颜色的数量不可能相等——棋盘无法铺满。当 n = 3k + 2 时，数量同样不相等。

We conclude: a 2 × n rectangle can be tiled by L-triominoes if and only if n is divisible by 3. This demonstrates the power of three-color counting arguments.

我们得出结论：2 × n 的矩形可以被 L 形三连块铺满当且仅当 n 是 3 的倍数。这展示了三色计数论证的威力。

5. Example 3: Path Coloring on a Grid | 例 3：网格上的路径染色

Problem: In a 3 × 3 grid, can a path visit every cell exactly once and return to the start, such that with a fixed three-coloring of the grid, each move changes color?

问题：在 3 × 3 网格中，是否存在一条路径恰好经过每个格子一次并返回起点，并且在一个固定的三色染色下，每一步都改变颜色？

Solution: Color the 3 × 3 grid in a checkerboard-like 3-color pattern:

解答：将 3 × 3 网格按类似于棋盘格的三色图案染色：

A	B	C
B	C	A
C	A	B

In this coloring, each color appears exactly 3 times. A Hamilton cycle on the 3 × 3 grid has 9 vertices and 9 edges. Since every move changes color, the sequence of colors along the cycle is a cycle of length 9 in a 3-color graph — but in a proper 3-coloring of a cycle, the length must be a multiple of 2 if we use only two colors, or if three colors are used, consecutive distinct colors force the first and last vertex to satisfy a parity condition.

在这种染色中，每种颜色恰好出现 3 次。3 × 3 网格上的哈密顿回路有 9 个顶点和 9 条边。由于每一步都改变颜色，沿回路的颜色序列是 3 色图中的一个长度为 9 的环——但在一个环中，如果只用两种颜色正确染色，长度必须是 2 的倍数；如果使用三种颜色，相邻颜色不同的条件会给首尾顶点施加奇偶约束。

More directly: in the above coloring, moving from A always leads to B; from B always leads to C; from C always leads to A. Thus the color sequence must be a repetition of A-B-C-A-B-C-…, forming a cycle of length divisible by 3. But the cycle length is 9, which is divisible by 3, so no immediate contradiction arises from periodicity alone.

更直接地：在上述染色中，从 A 出发必然到 B；从 B 出发必然到 C；从 C 出发必然到 A。因此颜色序列必然是 A-B-C-A-B-C-… 的循环重复，形成长度可被 3 整除的环。而回路长度为 9，可以被 3 整除，因此仅从周期性来看并不会立刻产生矛盾。

However, a closer look at the grid shows that some edges connect A to C (for example, the edge from top-right C to middle-right A), violating the rule that every move changes color under the strict A→B→C→A ordering. In a problem where “changes color” simply means “not the same color,” those edges are allowed — so we must be careful with our assumptions.

然而，仔细观察网格会发现有些边连接 A 和 C（例如右上角 C 到中右 A 的边），这违反了在严格 A→B→C→A 顺序下“每一步都改变颜色”的规则。不过如果“改变颜色”仅仅意味着“颜色不同”，这些边是允许的——所以我们必须小心对待假设条件。

To derive a definitive conclusion, use a parity argument with the Hamiltonian cycle: since the grid is bipartite with 9 vertices, a Hamiltonian cycle cannot exist because a bipartite graph with an odd number of vertices has no Hamiltonian cycle. The three-coloring alone yields the constraint that color changes alternate, but the deeper obstruction is bipartiteness.

为了得出确定结论，我们对哈密顿回路使用奇偶论证：由于网格是二分图且有 9 个顶点，而奇数个顶点的二分图不存在哈密顿回路。三色染色本身给出的是颜色交替变化的约束，但更本质的障碍在于二分图的结构。

6. The Modulo 3 Value-Sum Technique | 模 3 赋值求和技巧

One of the most versatile techniques in three-color problems is assigning the values 0, 1, 2 to the colors and tracking the sum modulo 3. If every allowed operation changes the sum by a fixed amount, we can often prove impossibility.

三色问题中最通用的技巧之一，是给三种颜色赋予 0、1、2 的数值，然后追踪总和模 3 的变化。如果每个允许的操作都使总和改变固定的量，我们往往能证明不可能性。

For example, in a problem where we replace three consecutive cells in a 1 × n strip with colors (a, b, c) by (a+1, b+1, c+1) modulo 3, the total sum modulo 3 stays invariant. Any configuration reachable from the initial state must preserve the sum modulo 3.

例如，在一个 1 × n 长条中，每次操作将三个连续格子的颜色 (a, b, c) 替换为 (a+1, b+1, c+1)（模 3），那么总和模 3 保持不变。任何从初始状态可达的构型都必须保持总和模 3 不变。

Similarly, switching colors cyclically (A→B→C→A) on a subset can change the sum in a controlled way. Comparing the required change with the actual change often yields a contradiction.

类似地，在一个子集上循环切换颜色（A→B→C→A）可以使总和按可控方式变化。将所需变化与实际变化进行比较，往往能得到矛盾。

The value-assignment technique is especially effective when combined with counting arguments, because it links color patterns with algebraic invariants.

赋值技巧与计数论证结合时尤其有效，因为它将颜色模式与代数不变量联系了起来。

7. Using Three-Coloring to Prove the Existence of a Monochromatic Structure | 用三色染色证明单色结构的存在

Sometimes three-coloring is used in reverse: instead of proving impossibility, we prove that any three-coloring of a certain configuration must contain a monochromatic substructure. This is the essence of Ramsey-type arguments.

有时三色染色的用途是反向的：不是证明不可能，而是证明任意三色染色都必然包含某个单色子结构。这正是拉姆齐型论证的核心。

A classic example: In any three-coloring of the edges of K₆ (the complete graph on 6 vertices), there exists a monochromatic triangle. The standard proof considers one vertex, which is incident to 5 edges. By the pigeonhole principle, at least 3 of these edges share the same color, say red, connecting to vertices X, Y, Z.

一个经典例子：对 K₆（6 个顶点的完全图）的边进行任意三色染色，必然存在一个单色三角形。标准证明考虑一个顶点，它有 5 条关联边。根据鸽巢原理，至少有 3 条边同色，设为红色，连接顶点 X、Y、Z。

If any edge among X, Y, Z is red, we have a red triangle. Otherwise, the triangle XYZ must be colored entirely with the other two colors. But a two-coloring of K₃ (a triangle) does not guarantee a monochromatic edge — the triangle could be green-blue-green-blue… wait, with three vertices and two colors, by pigeonhole two edges share a color, but they may not form a triangle.

如果 X、Y、Z 中任意一条边是红色，则构成红色三角形。否则，三角形 XYZ 必须完全用另外两种颜色染色。然而，用两种颜色对 K₃（三角形）染色并不保证出现单色边——三角形可以是绿-蓝-绿-蓝……等等，三个顶点用两种颜色，根据鸽巢原理必有两边同色，但这两条边未必构成三角形。

Actually, for two colors, any coloring of K₃ does contain a monochromatic edge. But for a monochromatic triangle, we need all three edges the same — which is not guaranteed. Hence, K₆ guarantees a monochromatic triangle under three-coloring, whereas K₅ does not. This is the famous Ramsey number R(3,3,3) = 17 for monochromatic triangles with three colors — but for K₆ the statement is about a forced single-color triangle only under the condition that the other two colors appear…

实际上，对于两种颜色，K₃ 的任意染色确实包含一条单色边。但对于单色三角形，我们需要三条边全都同色——这并不保证。因此，K₆ 在三种颜色染色下保证单色三角形，而 K₅ 则不然。关于三个颜色下单色三角形的著名拉姆齐数是 R(3,3,3) = 17——但对于 K₆ 而言，论断是关于被强制出现的同色三角形，前提是另外两种颜色的边不足以避免它……

Wait — let us clarify. The edge-coloring of K₆ with three colors: pick a vertex, five incident edges; by pigeonhole, at least ⌈5/3⌉ = 2 edges share a color, not 3. To force 3, we need degree 7, i.e., K₈. Let us redo: In K₇, each vertex has degree 6; by pigeonhole, among 6 edges at least 2 share a color, but not 3. So K₆ does not suffice. The correct statement: R(3,3,3) = 17, meaning any three-edge-coloring of K₁₇ contains a monochromatic triangle, and K₁₆ avoids it.

等等——需要澄清。对 K₆ 的边进行三色染色：选取一个顶点，5 条关联边；根据鸽巢原理，至少有 ⌈5/3⌉ = 2 条边同色，而不是 3 条。要强行得到 3 条同色边，需要度为 7，即 K₈。重新计算：在 K₇ 中，每个顶点的度为 6；根据鸽巢原理，6 条边中至少有 2 条同色，但不是 3 条。因此 K₆ 是不够的。正确的论断是：R(3,3,3) = 17，意味着 K₁₇ 的任意三边染色都包含单色三角形，而 K₁₆ 则没有。

The correct classic example for three colors using pigeonhole is: in any edge-coloring of K₁₇ with three colors, there is a monochromatic triangle. The proof uses a careful degree-based argument: each vertex has degree 16; among 16 incident edges, by pigeonhole at least ⌈16/3⌉ = 6 share one color. Then among those 6 vertices, if any internal edge has that same color, we are done; otherwise, the K₆ induced is colored with only two colors — and we know R(3,3) = 6, so there is a monochromatic triangle in one of those two colors.

关于三种颜色的正确经典例子是：K₁₇ 的任意三边染色中必含单色三角形。证明使用基于度的精细论证：每个顶点度为 16；在 16 条关联边中，根据鸽巢原理，至少有 ⌈16/3⌉ = 6 条同色。在这 6 个顶点中，如果存在任意一条内部边也为此色，则已完成；否则，对应的 K₆ 子图只有两种颜色——而我们知道 R(3,3) = 6，因此在这两种颜色之一中必有一个单色三角形。

8. Geometric Three-Coloring: Covering Problems | 几何三色染色：覆盖问题

In geometry, three-colorings are often used to disprove coverings or to prove the existence of certain points with prescribed color relationships. A common configuration is the 3 × 3 grid of points, or the vertices of a regular polygon.

在几何中，三色染色常用于否定某个覆盖方案，或证明存在具有指定颜色关系的点。常见的构型是 3 × 3 的点阵，或正多边形的顶点。

Problem: Prove that in any three-coloring of the 3 × 3 grid of points, there exist two points of the same color separated by exactly the distance of the grid diagonal.

问题：证明在 3 × 3 点阵的任何三色染色中，都存在两个同色点，它们之间的距离恰好等于网格对角线的长度。

Solution: Consider the 4 corners of the 3 × 3 grid. They form a square of side length 2 (in unit spacing). The distance between opposite corners is the diagonal of length 2√2. The four corners cannot all have distinct colors because only three colors are available, so two corners must share a color.

解答：考虑 3 × 3 点阵的四个角。它们构成一个边长为 2（单位间距）的正方形。对角顶点之间的距离为对角线的长度 2√2。因为只有三种颜色，四个角不可能全部颜色不同，所以必有两个角同色。

If the two same-colored corners are adjacent, their distance is 2, which is not the diagonal. If they are opposite, the distance is exactly the diagonal of a unit square (√2) for the inner grid, not 2√2. So we must refine our argument: look at all 2 × 2 subsquares. Each subsquare has 4 vertices; by pigeonhole, two share a color.

如果两个同色角相邻，它们的距离是 2，不是对角线距离。如果它们相对，距离是单位网格的对角线（√2），也不是 2√2。因此需要改进论证：考察所有 2 × 2 的子方格。每个子方格有 4 个顶点；根据鸽巢原理，必有两个同色。

Actually, a cleaner statement uses unit distance. In any three-coloring of the 3 × 3 grid points, there exist two points of the same color at unit distance? The answer is no — a checkerboard-like coloring with three colors can avoid same-color unit pairs… The precise result depends on the structure. Competitive problems usually specify which distance is forced.

实际上，更简洁的论断是单位距离。在 3 × 3 点阵的任意三色染色中，是否存在单位距离的同色点？答案是否定的——用类似棋盘格的三色图案可以避免同色单位对……具体结果依赖于结构。竞赛问题通常会指明究竟强制哪个距离。

9. The Continuity/Transition Counting Method | 连续性/过渡计数法

Another powerful tool is counting color transitions along a closed curve or a path. If a configuration has a certain number of transitions, constraints on that number can rule out a coloring.

另一个强大工具是沿着闭合曲线或路径统计颜色转移的次数。如果某个构型具有特定的转移次数，那么关于该次数的约束条件可以排除某种染色。

Consider a cycle of vertices v₁, v₂, …, vₙ, v₁. Define a transition as an edge whose endpoints have different colors. With three colors, a properly colored cycle (no monochromatic edge) has transitions everywhere. If we require the pattern to be periodic with period 3, the number of vertices must be a multiple of 3.

考虑顶点环 v₁, v₂, …, vₙ, v₁。定义一条边如果两个端点颜色不同则称为一次颜色转移。在三种颜色下，一个正常染色的环（没有单色边）处处都是转移。如果要求颜色模式以 3 为周期，那么顶点数必须是 3 的倍数。

This simple observation can be combined with other counting arguments. For example, if a Hamiltonian cycle on a graph with n vertices must visit all colors equally, then n must be divisible by 3.

这个简单的观察可以与其他计数论证结合。例如，如果一个图上的哈密顿回路必须等量地经过所有颜色，那么 n 必须是 3 的倍数。

Transition counting is particularly useful in problems about cyclic arrangements, seating problems, and arrangements around a circle.

转移计数在关于循环排列、座位问题和圆周排列的问题中尤其有用。

10. Construction Techniques: Achieving a Given Color Distribution | 构造技巧：实现给定的颜色分布

Many problems ask not only for impossibility proofs but also for the demonstration that certain color distributions are attainable. A systematic construction method is to use periodic block colorings, then adjust via local swaps.

许多问题不仅要求不可能性证明，还要求展示某种颜色分布是可以实现的。一个系统的构造方法是使用周期性块染色，然后通过局部交换进行调整。

For instance, to color a 3 × n grid so that each column has all three colors and adjacent cells (horizontally) of the same row differ, we can repeat the pattern:

例如，要对 3 × n 网格染色，使得每一列都有三种颜色且同一行相邻格子颜色不同，可以重复以下模式：

A	B	C	A
B	C	A	B
C	A	B	C

This cyclic Latin arrangement works when the number of columns is arbitrary. When constraints are tighter, such as requiring each color to appear exactly k times in the whole grid, we can begin with the periodic pattern and then perform color swaps along closed cycles to adjust counts without violating local constraints.

这种循环拉丁排列在列数任意时都成立。当约束更紧时（例如要求每种颜色在整个网格中恰好出现 k 次），我们可以从周期模式出发，然后沿着闭合回路进行颜色交换来调整计数，同时不违反局部约束。

The key to construction problems is to identify the degrees of freedom: which local rearrangements preserve the constraints? Starting from a valid configuration, exploring these rearrangements often leads to a full characterization of attainable distributions.

构造问题的关键在于识别自由度：哪些局部重排能保持约束？从一个有效构型出发，探索这些重排方式往往能获得对可实现分布的完整刻画。

11. Common Pitfalls and How to Avoid Them | 常见误区与规避方法

Pitfall 1: Assuming equal color counts. A triomino covering three colors implies equal counts only if the board itself has equal counts. Always check the initial color distribution of the board.

误区一：假设颜色数量相等。三连块覆盖三种颜色并不意味着整个棋盘等量，只有当棋盘本身的颜色分布恰好相等时才成立。务必先检查棋盘初始的颜色分布。

Pitfall 2: Misapplying the pigeonhole principle. For three colors, 4 objects guarantee two of the same color, but 3 objects do not. In degree arguments, be careful: degree 5 with 3 colors guarantees only ⌈5/3⌉ = 2 same-colored edges, not 3.

误区二：误用鸽巢原理。三种颜色下，4 个对象保证有两个同色，但 3 个对象不保证。在度数论证中要小心：度为 5 且有 3 种颜色只能保证 ⌈5/3⌉ = 2 条同色边，而不是 3 条。

Pitfall 3: Confusing “different colors” with “cyclically consecutive colors.” In many problems, adjacent cells must have different colors (no restriction on which pair). In others, the color must shift cyclically A→B→C→A. The distinction fundamentally changes the problem.

误区三：混淆“颜色不同”与“循环相邻颜色”。许多问题只要求相邻格子颜色互不相同（不限制具体是哪一对）。另一些问题则要求颜色必须按 A→B→C→A 循环转移。这个区别会从根本上改变问题的性质。

Pitfall 4: Forgetting modular arithmetic. When assigning values 0, 1, 2 to colors, remember all calculations are modulo 3. Do not mix ordinary equality with congruence.

误区四：忘记模运算。当给颜色赋值 0、1、2 时，所有计算都要模 3。不要把普通等式与同余混为一谈。

12. Strategic Summary and Practice Advice | 策略总结与练习建议

To master three-coloring problems, build a mental checklist:

要掌握三色染色问题，请建立一份解题检查清单：

Determine what the three colors represent and what the constraints really say.

确定三种颜色代表什么，约束的真正含义是什么。
Try assigning numerical values (0, 1, 2) to colors and explore invariants modulo 3.

尝试给颜色赋数值 (0, 1, 2)，并探索模 3 的不变量。
Count the number of cells/vertices of each color in the initial configuration.

数一数初始构型中每种颜色的格子/顶点数量。
Identify local objects (triominoes, edges, triangles) that interact with all three colors equally.

识别那些与三种颜色等量作用的局部对象（三连块、边、三角形等）。
Construct candidate colorings using periodic or cyclic patterns, then test them against the constraints.

使用周期或循环模式构造候选染色方案，然后检验其是否满足约束。
If impossibility is suspected, isolate the invariant that blocks the configuration.

如果怀疑不可能，则找出阻止该构型出现的不变量。

Practice with problems from past olympiads, starting with simple grids and graph colorings, then progressing to more complex geometric configurations. Over time, the patterns of thought — invariant detection, modular counting, and constructive iteration — will become second nature.

用历年竞赛真题进行训练，从简单的网格和图染色开始，再逐步过渡到更复杂的几何构型。经过一段时间，这些思维模式——不变量检测、模计数和构造迭代——将变得如同本能一般。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Three-Coloring Problems in Math Competitions: A Systematic Approach | 数学竞赛考点：三色染色问题解题思路精讲