MathLabs

第3题

有 4n4n 颗石子,重量分别为 1,2,3,…,4n1, 2, 3, \ldots, 4n。每颗石子被染成 nn 种颜色之一,且每种颜色恰有四颗石子。证明可以把这些石子分成两堆,使得两堆的总重量相等,并且每堆恰好包含每种颜色各两颗石子。
第 2/6 步:把颜色变成4正则图
通俗地说

把每种颜色收缩成一个顶点,细绳就变成了图的边,统计关联次数可知每个顶点的度数都相同。

deg⁡G(v)=4 for every vertex v.\deg_G(v)=4\ \text{for every vertex}\ v.
详细分析

把 4n 颗石子按颜色分成 n 个盒子,每盒四颗,令 G 是以这些盒子为顶点、以这 2n 条细绳为边的多重图,其中连接同色两颗石子的细绳在该顶点处变成一个贡献为2的自环。由于每个盒子恰有4颗石子,且每颗石子恰是一条细绳的一个端点,G 的每个顶点度数都恰为4,且 G 在 n 个顶点上共有 2n 条边。