证 明 题（数学·2020年9月·国际数学奥林匹克）

There are 4n pebbles of weights 1,2,3,…,4n. Each pebble is coloured in one of n colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:

● The total weights of both piles are the same.

● Each pile contains two pebbles of each colour.

有 4n 枚石子，重量分别为 1 , 2 , 3 , … ， 4n ．每一枚小石子都染了n种颜色之一，使得每种颜色的小石子恰有四枚．证明：可以把这些小石子分成两堆，且满足以下两个条件：

● 两堆小石子的总重量相同；

● 每堆中每种颜色的小石子各有两枚．

(匈牙利供题)

解答提示

证明：设n种颜色为 c1 ，c2， … , cn , 小石子集合记为｛ p1 , p2 ，… ，p4n｝ . pi表示重量为 i 的小石子．下面构造图 G=（V, E )，其中顶点集 V ＝{c1, c2, … , cn } ，边集的定义如下 ：对每个 1 ≤ i ≤ 2n ．若 pi的颜色为u，p4n+1-i的颜色为 v。，则在u ，v之间连一条边，对应于小石子对(pi,p4n+1-i)．这样 G 共有 2n 条边，可能含环边（当pi与p4n +1-i同色时）或重边，由于每种颜色的小石子恰有四枚．因此 G 是 4-正则图（注意，一条环边在顶点处需计入度数 2 ) .我们证明下面的引理：引理：任何一个 4-正则图都有一个 2-正则生成子图．引理的证明：只需对连通图来证明，一般情形对每个连通分支取 2-正则生成子图即可．假设 G = (V,E）是一个连通的 4-正则图，|V|=n，|E|=2n ．由于每个项点处的度数均为偶数，由欧拉一笔画定理， G 中存在一个欧拉闭迹 L . 将 L 中的边交替地分到集合 E1 ，E2中，则|E1|=|E2|=n。且（V, E1) ,（V,E2）均是 2-正则生成子图．事实上，考察一个顶点v，若v处...

查看完整答案，请下载word版