6元集之2 元幂集的组合趣题

hujunhua

试证明：如果6元集{a,b,c,d,e,f}的某6个二元子集含有a,b,c,d,e,f恰好各2个，那么这6个二元子集必可三三分成2组，每组含有a,b,c,d,e,f 恰好各1个.

mathe

{ab,bc,ca,de,ef,df}

hujunhua

难怪我找不到非穷举的证明，原来是有反例。 忽视这种反例，是因为我在选择6个2元子集时，总是自动地（出于工作中线性无关的需要）回避较短的闭链。所谓闭链，比如｛ab, bc, ca}, 3个二元子集恰含有a,b,c,d,e,f中的3个特定元各2重，即为3-闭链。 一个闭链如果包含2个或者2个以上的较短闭链，则称为多环闭链。 且将如{ab, cd, ef}这样恰好覆盖{a,b,c,d,e,f}的三元子集组称为一个覆盖组。我想说的应该是：一个单环6-闭链，必可划分为2个覆盖组。 挖出单环这个条件后，应该容易证明了。