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 を含む部分集合の代表元はそれに固定される。