📚 Party Unity: A Ramsey Theory Approach in Edexcel A-Level Decision Mathematics | 派对团结：拉姆齐理论在爱德思 A-Level 决策数学中的应用
How can you guarantee that at any party with six people, there will always be a group of three who are either all mutual friends or all mutual strangers? This classic ‘party unity’ problem lies at the heart of Ramsey theory, a beautiful branch of combinatorics that finds its way into Edexcel A-Level Decision Mathematics 1 (D1). By modelling social connections as graphs and colouring edges, you will learn to apply rigorous reasoning to prove that complete disorder is impossible beyond a certain size – a powerful idea with deep implications for networks, scheduling and algorithm design.
在任何六人参加的派对中，为什么总能保证存在三人要么彼此都是朋友、要么彼此都是陌生人？这个经典的“派对团结”问题是拉姆齐理论的核心，而拉姆齐理论作为组合数学的一个优美分支，已被纳入爱德思 A-Level 决策数学 D1 的考查范围。通过将社交关系建模为图并对边进行着色，你将学会运用严格推理证明：超过一定规模后，完全无序是不可能的——这一深刻的思想对网络、调度和算法设计具有重要影响。
1. What Is the Party Unity Problem? | 什么是派对团结问题？
Imagine hosting a party. You are interested in the relationships between guests: for any two individuals, they either know each other (friends) or do not know each other (strangers). The party unity problem asks a simple but profound question: what is the smallest number of guests required to guarantee that there will be a threesome who all share the same type of relationship – three mutual friends or three mutual strangers? Intuitively, with only three or four people, you can easily avoid such a unified trio. The surprise is that the magic number is six.
想象你举办一场派对。你关心宾客之间的关系：任意两个人要么认识（朋友），要么不认识（陌生人）。派对团结问题提出了一个简单却深刻的问题：需要至少多少位宾客，才能保证必然存在一个三人组，其内部关系完全相同——要么都是朋友，要么都是陌生人？直觉上，如果只有三或四人，很容易避开这种统一的三人组。令人惊讶的是，这个神奇的数字是六。
In A-Level Decision Mathematics (D1), algorithms and proofs often rely on the principle that certain structures must emerge once a system is large enough. The party unity problem is the perfect entry point to Ramsey theory, specifically the Ramsey number R(3,3)=6, where the first ‘3’ stands for the desired size of a ‘friends’ clique and the second ‘3’ for a ‘strangers’ clique. This problem is entirely self-contained, using only basic graph terminology and logical deduction – exactly the skills tested in your D1 exam.
在 A-Level 决策数学 D1 中，算法和证明常常依赖于这样一个原理：一旦系统足够大，某些结构必然会出现。派对团结问题是进入拉姆齐理论的绝佳切入点，具体涉及拉姆齐数 R(3,3)=6，其中第一个‘3’代表所求的“朋友团”规模，第二个‘3’代表“陌生人团”规模。该问题完全自包含，仅使用基本的图论术语和逻辑演绎——这正是 D1 考试所考查的技能。
2. Modelling the Party as a Complete Graph | 将派对建模为完全图
To turn the party into a mathematical object, we represent each guest as a vertex (node). Every pair of guests is connected by an edge, because there is a definite relationship (friends or strangers) between them. This gives a complete graph on n vertices, denoted Kₙ. The edges are then coloured using two colours: red for ‘friends’ and blue for ‘strangers’. The party unity goal is to find a monochromatic triangle – three vertices such that all three edges among them share the same colour.
为了把派对转化为数学对象，我们将每位宾客表示为一个顶点（节点）。每对宾客之间用一条边连接，因为他们之间有一种确定的关系（朋友或陌生人）。这样便得到了一个n个顶点的完全图，记作 Kₙ。接着给边着色，用两种颜色：红色表示“朋友”，蓝色表示“陌生人”。派对团结的目标是找到一个单色三角形——即三个顶点，它们之间的三条边颜色完全相同。
This modelling step is typical of D1 problems: we simplify a real-world scenario into a graph, apply definitions (vertices, edges, degree, subgraph) and then search for a property. The complete graph K₆ has 6 vertices and 15 edges. Each edge is either red or blue, making 2¹⁵ possible colourings. We must prove that in every single one of these colourings, a monochromatic triangle exists.
这一建模步骤是 D1 问题的典型做法：我们将现实场景简化成一个图，应用定义（顶点、边、度、子图），然后寻找某种性质。完全图 K₆ 有 6 个顶点和 15 条边。每条边要么是红色要么是蓝色，共有 2¹⁵ 种可能的着色方案。我们必须证明在每一种着色方案中，都必然存在一个单色三角形。
3. Defining Key Graph Terms for D1 | D1 中的关键图术语定义
Before tackling the proof, let us revise some essential Decision Mathematics terminology. A ‘complete graph’ is a graph in which every pair of distinct vertices is connected by a unique edge. The ‘degree’ of a vertex is the number of edges incident to it – in Kₙ, every vertex has degree n−1. A ‘subgraph’ is a graph whose vertices and edges are a subset of those in the original graph. A ‘clique’ is a complete subgraph.
在开始证明之前，我们先复习一些决策数学的基础术语。“完全图”是指任意两个不同顶点之间都恰有一条边相连的图。顶点的“度”是指与该顶点相连的边的条数——在 Kₙ 中，每个顶点的度都是 n−1。“子图”是指顶点集和边集均是原图子集的图。“团”是一个完全子图。
A ‘colouring’ of the edges is an assignment of colours to edges. With two colours, say red and blue, we speak of a 2-colouring of edges. The ‘neighbourhood’ of a vertex v in a coloured graph is often considered separately for each colour; for a given vertex, we count how many red edges and how many blue edges are incident to it. Understanding these concepts is vital for following the Ramsey argument and for many D1 graph algorithms, such as Kruskal’s or Prim’s.
“边着色”是指为边指定颜色。使用两种颜色，如红色和蓝色，我们称之为边的 2-着色。在着色图中，一个顶点 v 的“邻域”通常按颜色分别考虑；对于给定顶点，我们计算它发出的红边数和蓝边数。理解这些概念对于跟上拉姆齐论证的节奏以及许多 D1 图算法（如克鲁斯卡尔算法或普里姆算法）至关重要。
4. The Proof Setup: Focusing on One Vertex | 证明准备：聚焦一个顶点
Take any 2-colouring of K₆. Pick an arbitrary vertex and label it A. Vertex A is connected to the other five vertices (B, C, D, E, F) by five edges. Because there are only two colours available, by the pigeonhole principle, at least three of these five edges must share the same colour. Without loss of generality, assume there are three red edges from A – say to vertices B, C and D. We will now consider the triangle formed by B, C and D.
取 K₆ 的任意一种 2-着色。任选一个顶点，标为 A。顶点 A 与其他五个顶点（B, C, D, E, F）之间有五条边相连。由于只有两种颜色，根据鸽巢原理，这五条边中至少有三条颜色相同。不失一般性，假设有三条红边从 A 发出，分别连向顶点 B、C 和 D。现在我们考虑由 B、C、D 构成的三角形。
This choice is the crux of the entire proof. By selecting a vertex and looking at its incident edges, we break down the global problem into a local one. The setup is reminiscent of D1 algorithms that repeatedly examine a vertex’s connections, such as finding a minimum spanning tree or checking for a Hamiltonian cycle. Here, we only need pure logic to draw the conclusion.
这一选择是整个证明的关键。通过选取一个顶点并观察它的关联边，我们把整体问题分解为局部问题。这种设置方式类似 D1 中反复检查顶点连接的算法，例如寻找最小生成树或检查哈密顿回路的算法。而在这里，我们仅需纯逻辑便可得出结论。
5. Proving the Monochromatic Triangle | 证明单色三角形
Now inspect the three edges between B, C and D: B–C, C–D, and D–B. If any one of these edges is red, then together with the two red edges from A to those two vertices, we obtain a red triangle. For instance, if B–C is red, then A–B–C–A is a red triangle. On the other hand, if none of the edges among B, C and D is red, then all three must be blue, forming a blue triangle. In either case, a monochromatic triangle exists.
现在观察 B、C、D 之间的三条边：B–C、C–D 和 D–B。如果这三条边中任何一条是红色，那么加上从 A 到那两点的两条红边，我们就得到一个红色三角形。例如，若 B–C 为红，则 A–B–C–A 便是红色三角形。反之，若 B、C、D 之间没有红边，则它们必定全是蓝色，构成一个蓝色三角形。无论哪种情况，单色三角形都必然存在。
This completes the proof that R(3,3) ≤ 6, meaning that six people are enough to force a monochromatic K₃. It remains to show that five people are not enough, which is done by counterexample: colour the edges of K₅ so that it forms a red 5-cycle and a blue 5-cycle (the complement), and you will find no monochromatic triangle. Therefore R(3,3) = 6 exactly. For a D1 student, understanding this counterexample demonstrates the ability to test a bound and appreciate the sharpness of the result.
这样便完成了 R(3,3) ≤ 6 的证明，意味着六人足以必然产生一个单色 K₃。尚需证明五人不够，这通过反例来完成：给 K₅ 的边着色，使得其形成一个红色五边形环和一个蓝色五边形环（互为补图），你会发现没有任何单色三角形。因此，R(3,3) 确切等于 6。对 D1 学生来说，理解这个反例展示了检验边界的能力，并体会到结果的精确性。
6. Why K₅ Fails: The Counterexample | K₅ 为何失败：反例
Draw five vertices arranged in a circle. Colour the five outer edges red, and the five inner diagonals blue. Alternatively, you can pair vertices such that the red graph is a cycle of length 5: 1–2–3–4–5–1 (in red), and all other edges are blue. Check every set of three vertices: in the red subgraph, there is no triangle because a pentagon contains no 3-cycles; in the blue subgraph, the complement of a 5-cycle is another 5-cycle, also triangle-free. Hence K₅ can be 2-coloured without a monochromatic triangle.
画五个顶点排成一圈。将五条外圈边着红色，五条内对角线着蓝色。或者，你也可以配对顶点使得红色图是一个长为 5 的圈：1–2–3–4–5–1（红色），其余所有边都是蓝色。检查每一个三点组合：在红色子图中，因为没有三角形（五边形不包含三边形）；在蓝色子图中，5-圈的补图是另一个 5-圈，同样无三角形。因此，K₅ 可以被 2-着色而不产生单色三角形。
This counterexample is a standard exercise in D1 applied graph theory. It also provides a good opportunity to practise working with adjacency matrices or lists. For Edexcel exams, you might be asked to sketch such a colouring and explain why it avoids a monochromatic K₃, testing your ability to reason about subgraph structures and edge colourings.
这个反例是 D1 应用图论中的标准练习。它也提供了一个练习使用邻接矩阵或邻接表的好机会。在爱德思考试中，你可能会被要求画出这样一种着色并解释它为何避开了单色 K₃，以此考查你对子图结构和边着色的推理能力。
7. The Role of the Pigeonhole Principle | 鸽巢原理的作用
The pigeonhole principle states that if n items are placed into m containers and n > m, then at least one container must contain at least two items. In the proof for K₆, the ‘items’ are the five edges from A, the ‘containers’ are the two colours; with 5 > 2×2, we cannot guarantee evenly distributed colours, but the exact argument uses the ceiling: at least ⌈5/2⌉ = 3 edges share a colour. This simple counting principle underlies many D1 algorithms, such as bin packing and scheduling.
鸽巢原理指出：如果把 n 个物品放入 m 个容器中，且 n > m，那么至少有一个容器包含至少两个物品。在 K₆ 的证明中，“物品”是从 A 发出的五条边，“容器”是两种颜色；虽然不能直接说 5 > 2×2，但确切的论证使用了取整：至少有 ⌈5/2⌉ = 3 条边同色。这个简单的计数原理是许多 D1 算法（如装箱和调度）的基础。
In your exam, you may be asked to identify where the pigeonhole principle kicks in or to apply it in a different Ramsey-style scenario. For example, ‘What is the minimum number of edges from a vertex in a complete graph of size 7 coloured with three colours to guarantee three of the same colour?’ The answer uses ⌈(7−1)/3⌉ = 2? Actually, with 3 colours and 6 edges, by pigeonhole principle, at least ⌈6/3⌉ = 2 edges share a colour, but for three edges we need a different bound. Such extensions sharpen your combinatorial reasoning.
在考试中，你可能会被问到鸽巢原理在何处生效，或者要求将其应用到不同的拉姆齐式场景中。例如，“用三种颜色对一个大小为 7 的完全图的边着色时，从一个顶点引出的边中最少有多少条同色，才能保证存在三条同色边？”答案用 ⌈(7−1)/3⌉ = 2，但要保证三条同色边需要不同的界限。这类扩展能强化你的组合推理能力。
8. Connections to Edexcel D1 Graph Algorithms | 与爱德思 D1 图算法的关联
While Ramsey theory itself may only appear in extension tasks, its core techniques – systematic case analysis, bounding, and logical deduction – are directly applicable to the D1 syllabus. For instance, when determining whether a graph contains a Hamiltonian cycle, you often argue that if a vertex has degree less than n/2, certain shortcuts must exist. Similarly, in critical path analysis, you deduce the minimum project duration by considering all possible dependencies. The Ramsey proof trains the same ‘forced existence’ reasoning.
尽管拉姆齐理论本身可能仅出现在拓展任务中，但其核心技巧——系统化的情形分析、边界推定和逻辑演绎——可直接应用于 D1 课程。例如，在判断一个图是否包含哈密顿回路时，你经常需要论证，若某顶点的度小于 n/2，则必然存在某些捷径。类似地，在关键路径分析中，你通过考虑所有可能的依赖关系来推导项目的最短持续时间。拉姆齐证明训练的正是这种“必然存在”的推理方式。
Many D1 exam questions require you to construct a rigorous argument showing that a certain configuration is unavoidable or that an algorithm terminates in a specific number of steps. Practising Ramsey-style puzzles hones your ability to present clear, step-by-step logical proofs – a skill that will boost your score on wordy graph theory and network flow items.
许多 D1 考题要求你构建严密论证，以说明某种构型不可避免，或某个算法在特定步数内终止。练习拉姆齐式谜题能磨炼你呈现清晰、一步步逻辑证明的能力——这一技能将提高你在文字描述较多的图论和网络流题目中的得分。
9. Generalising to Larger Ramsey Numbers | 推广到更大的拉姆齐数
The concept of party unity extends naturally: R(s, t) is the smallest n such that any red-blue colouring of Kₙ contains either a red Kₛ (s mutual friends) or a blue Kₜ (t mutual strangers). We have proved R(3,3)=6. Other known values include R(3,4)=9, R(3,5)=14, R(4,4)=18, and R(4,5)=25. The precise value of R(5,5) is still unknown, although it is between 43 and 48 – a famous open problem that shows how quickly combinatorial complexity explodes.
派对团结的概念可以自然地扩展：R(s, t) 是最小的 n，使得对 Kₙ 的任意红蓝着色中，要么包含一个红色 Kₛ（s 个共同朋友），要么包含一个蓝色 Kₜ（t 个共同陌生人）。我们已经证明了 R(3,3)=6。其他已知的值包括 R(3,4)=9、R(3,5)=14、R(4,4)=18 和 R(4,5)=25。R(5,5) 的精确值至今未知，只知介于 43 与 48 之间——这个著名的开放问题显示了组合复杂性爆炸式增长的速度。
For Edexcel D1, you are not expected to memorise these higher Ramsey numbers, but you may encounter problems that ask you to find bounds for small cases, or to explain why R(3,4) > 8 by constructing a suitable colouring of K₈ without a red K₃ or blue K₄. These exercises deepen your appreciation of how edge colourings and subgraph searches interact, reinforcing the computational thinking needed for decision maths.
对于爱德思 D1，你不需要记住这些更大的拉姆齐数，但你可能会遇到要求寻找小情形下界的问题，或者要求通过构造一个合适的 K₈ 着色（不含红 K₃ 或蓝 K₄）来解释为什么 R(3,4) > 8。这类练习能加深你对边着色与子图搜索如何相互作用的体会，强化决策数学所需的计算思维。
10. Ramsey Theory in Real-World Networks | 拉姆齐理论在现实世界网络中的应用
At first glance, the party problem seems like a recreational puzzle, but its implications ripple through computer science, communications and even theoretical physics. In network design, Ramsey numbers give insight into unavoidable substructures in large-scale graphs, such as social networks or the internet. For example, in a network of routers, if you colour connections by latency (low/high), a monochromatic clique might represent a cluster of nodes all with mutually low latency – a desirable property for fault-tolerant systems.
乍看之下，派对问题像是一个趣味谜题，但它的影响波及计算机科学、通信甚至理论物理。在网络设计中，拉姆齐数为大规模图（如社交网络或互联网）中不可避免的子结构提供了洞见。例如，在路由器网络中，如果用延迟高低给连接着色，一个单色团可能代表所有节点相互之间都是低延迟的集群——这对于容错系统来说是一种理想性质。
Decision mathematics modules are designed to show you the practical power of discrete models. By exploring Ramsey theory, you see how an abstract combinatorial guarantee translates into engineering constraints. Moreover, the techniques used in deriving Ramsey bounds – constructive colourings, counting arguments, recursion – mirror the algorithmic design patterns you apply in Kruskal’s algorithm, Dijkstra’s algorithm, or the simplex method.
决策数学模块旨在向你展示离散模型的实用力量。通过探索拉姆齐理论，你将看到一条抽象的组合保证如何转化为工程约束。此外，推导拉姆齐界时使用的技术——构造性着色、计数论证、递归——与你应用克鲁斯卡尔算法、迪杰斯特拉算法或单纯形法时所使用的算法设计模式是类似的。
11. Exam-Style Question and Worked Solution | 考试风格题目与详细解答
Question: A party has six guests. Using the language of graph theory, prove that however the friendships and stranger relationships are arranged, there must exist a set of three guests who are all mutual friends or all mutual strangers. State the Ramsey number that your proof establishes.
题目：一个派对有六位宾客。用图论的语言证明，无论朋友关系与陌生人关系如何安排，总存在三位宾客，他们要么彼此都是朋友，要么彼此都是陌生人。指出你的证明所建立的拉姆齐数。
Mark scheme / Worked solution:
Model the guests as vertices of K₆. Colour each edge red if the two guests are friends, blue if they are strangers. Pick any vertex A. A has five incident edges. By the pigeonhole principle, at least three of them must share a colour; suppose they are red and lead to B, C, D. Now consider triangle BCD. If any edge in BCD is red, that edge together with A forms a red triangle. If no edge in BCD is red, all three are blue, forming a blue triangle. Hence in all cases a monochromatic K₃ exists. This proves that R(3,3) ≤ 6. Together with the counterexample on K₅, we have R(3,3) = 6.
评分标准 / 详细解答：
将宾客建模为 K₆ 的顶点。如果两位宾客是朋友，则将其间的边着红色；如果是陌生人，则着蓝色。任选一个顶点 A。A 有五条关联边。根据鸽巢原理，至少有三条边同色；假设它们是红色，并连接至 B、C、D。现在考虑三角形 BCD。若 BCD 中任意一边为红色，该边与 A 构成红色三角形。若 BCD 中没有红边，则三条边全为蓝色，构成蓝色三角形。因此，任何情况下均存在一个单色 K₃。这证明了 R(3,3) ≤ 6。再结合 K₅ 的反例，得到 R(3,3) = 6。
12. Strengthening Your Decision Mathematics Toolkit | 强化你的决策数学工具箱
The party unity problem might look like an elegant diversion, but it perfectly encapsulates the spirit of Edexcel Decision Mathematics: modelling, systematic reasoning, and the discovery of unavoidable patterns. As you revise for your D1 exam, try to formulate your own small Ramsey-style problems – for example, using three colours or searching for monochromatic K₄. Each attempt builds the critical skill of translating a fuzzy real-world situation into a crisp graph-theoretic statement.
派对团结问题或许看起来像一个优雅的消遣，但它完美地概括了爱德思决策数学的精神：建模、系统化推理，以及发现不可避免的模式。在你复习 D1 考试时，尝试自己提出一些小的拉姆齐式问题——例如，使用三种颜色或寻找单色 K₄。每一次尝试都会培养将模糊的现实情境转化为清晰的图论陈述这一关键技能。
Keep in mind that examiners reward clear, step-by-step logical arguments far more than raw memorisation. Whether you are tracing an algorithm on a graph or proving a Ramsey bound, always state your initial modelling choices, explain each inference, and finish with a concluding sentence that links back to the original problem. This structured approach, honed through the party unity proof, will serve you well across all topics in D1 – from linear programming to matchings and flows.
请记住，考官更看重清晰、步步推进的逻辑论证，而非死记硬背。无论你是在图上模拟算法，还是在证明一个拉姆齐界，始终要先阐明你的建模选择，解释每一步推理，并以一句联系回原问题的结束语收尾。这种结构化方法——经过派对团结证明的磨炼——将使你在 D1 的所有主题中受益，从线性规划到匹配与流。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导