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处...
查看完整答案