今週の問題 問57 答え

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

問57

集合U={a,b,c,d,e}がある。
Uから異なる部分集合を11個とりそれらをB1,B2,・・・,B11とする。
このとき必ずBi⊂Bjとなるようなi,j(i≠j)が存在することを示せ。

答え

Uの部分集合は32個ある。それらをグループ1から10に分類する。
グループ1: {} ⊂ {a} ⊂ {a,b} ⊂ {a,b,c} ⊂ {a,b,c,d} ⊂ {a,b,c,d,e}
グループ2: {b} ⊂ {b,c} ⊂ {b,c,d} ⊂ {b,c,d,e}
グループ3: {c} ⊂ {c,d} ⊂ {c,d,e} ⊂ {c,d,e,a}
グループ4: {d} ⊂ {d,e} ⊂ {d,e,a} ⊂ {d,e,a,b}
グループ5: {e} ⊂ {e,a} ⊂ {e,a,b} ⊂ {e,a,b,c}
グループ6: {a,c} ⊂ {a,c,e}
グループ7: {a,d} ⊂ {a,c,d}
グループ8: {b,d} ⊂ {a,b,d}
グループ9: {b,e} ⊂ {b,d,e}
グループ10: {c,e} ⊂ {b,c,e}

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

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする