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 中至少一个的代表元。
第 1/3 步：代表元向下传播
上一步下一步
r(X)=x1whenever x1=r(S) and x1∈Xr(X)=x_1\quad\text{whenever }x_1=r(S)\text{ and }x_1\in X
详细分析

记 r(X)r(X) 为 XX 的代表元，令 x1=r(S)x_1=r(S)。若 XX 含 x1x_1 且至多有 2012 个元素，用两个非空不交集将 XX 补足为 SS，条件迫使 r(X)=x1r(X)=x_1。若 XX 有 2013 个元素，先对每个含 x1x_1 的二元集应用条件，再对 XX 应用条件，同样得到结论。