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
詳しい解説

XX の代表元を r(X)r(X)、x1=r(S)x_1=r(S) とする。XX が x1x_1 を含み元数が2012以下なら、XXを二つの空でない互いに素な集合で補って SS にし、条件から r(X)=x1r(X)=x_1。XX が2013元なら、まず x1x_1 を含む各2元集合に条件を適用し、次に XX に適用すれば同じ結論を得る。