MathLabs

第2题

令 S={1,2,…,2014}S=\{1,2,\ldots,2014\}。对 SS 的每个非空子集 T⊆ST\subseteq S,从其元素中选一个代表元。求给所有非空子集分配代表元的方法数,使得当 D⊆SD\subseteq S 是三个非空子集 A,B,C⊆SA,B,C\subseteq S 的不交并时,DD 的代表元也是 A,B,CA,B,C 中至少一个的代表元。
第 2/3 步:选择被迫的链
x1,x2,…,x2010:2014⋅2013⋯5x_1,x_2,\ldots,x_{2010}:\quad 2014\cdot2013\cdots5
详细分析

x1x_1 有 2014 种选法。删去它,在剩余集合上重复论证,先选择 x2x_2,继续到 x2010x_{2010}。选择数为所示乘积;剩余集合中含最先出现的 xix_i 的每个子集代表元都被固定为它。