今週の問題　問57　答え｜数学の偏差値を上げて合格を目指す

当サイトは、PRを含む場合があります。

上野竜生です。問57の答えを発表します。

問57　★

集合U={a,b,c,d,e}がある。
Uから異なる部分集合を11個とりそれらをB₁,B₂,・・・,B₁₁とする。
このとき必ずB_i⊂B_jとなるようなi,j（i≠j)が存在することを示せ。

答え

Uの部分集合は32個ある。それらをグループ１から10に分類する。
グループ１：　{}　⊂　{a}　⊂　{a,b}　⊂　{a,b,c}　⊂　{a,b,c,d}　⊂　{a,b,c,d,e}
グループ２：　{b}　⊂　{b,c}　⊂　{b,c,d}　⊂　{b,c,d,e}
グループ３：　{c}　⊂　{c,d}　⊂　{c,d,e}　⊂　{c,d,e,a}
グループ４：　{d}　⊂　{d,e}　⊂　{d,e,a}　⊂　{d,e,a,b}
グループ５：　{e}　⊂　{e,a}　⊂　{e,a,b}　⊂　{e,a,b,c}
グループ６：　{a,c}　⊂　{a,c,e}
グループ７：　{a,d}　⊂　{a,c,d}
グループ８：　{b,d}　⊂　{a,b,d}
グループ９：　{b,e}　⊂　{b,d,e}
グループ10：　{c,e}　⊂　{b,c,e}

Uから異なる11個の部分集合をとると鳩ノ巣原理(部屋割り論法)より少なくとも1グループについて同じグループから2つ以上の部分集合が選ばれる。
その中から2つの集合B_i,B_jを選ぶとB_i⊂B_jまたはB_j⊂B_iのどちらかが成立する。
B_j⊂B_iならばiとjをひっくり返すことによりB_i⊂B_jにできるのでこれで題意は成立。