『部分集合』

◆秋田県　Alpha さんからの問題です。

【問題】

集合{0,1,2,3,4,5,6,7,8,9}から、5つの要素を持つ部分集合を10個取り出します。

これらの部分集合をS(1),S(2),…,S(10)とし、異なる自然数1≦i,j≦10に対して
集合S(i)∩S(j)の要素数をf(i,j)とおきます。

i,jが上記の条件を満たしながら動くとき、f(i,j)の最大値をMとします。

Mの最小値を求めてください。

◆山梨県　Footmark さんからの問題です。
詳しくは　【寄せられた解答】をご覧ください。

【追加問題１】

Ｍの最小値が３になる５つずつの１と０の並びの条件を求めてください。
ただし、１はその位置の要素を含むことを、０は含まないことをそれぞれ表すものとします。

◆秋田県　Alpha さんからの問題です。

【追加問題２】

前問において部分集合を10個取りだし、Mの最小値を3にしましたがMの最小値を3にしたまま取り出す部分集合はいくつまで増やすことができるでしょうか、
要素数5の11個の部分集合を取り出しても同じことができるでしょうか。
いくつまで可能かを答えてください。

【追加問題３】

前問において要素が5個の部分集合を取り出し、Mの最小値を3にしましたが、Mの最小値を3にしたまま取り出す部分集合の要素数をいくつまで増やすことができるでしょうか、
要素数6の部分集合を10個取り出しても同じことがいえるでしょうか。
いくつまで可能かを答えてください。

【追加問題４】

前問においては10の要素を持つ集合から、5要素数の部分集合を10個取り出しましたが、この5を2003に10を1338004に変更して同じような問題を作ります。
この場合もMの最小値は3であることを示してください。

つまり、要素数1338004の集合{0,1,2,…,1338003}から要素を2003個持つ1338004個の部分集合を取り出します。
この時、互いに異なるどの二つの部分集合に注目してもその共通部分の要素数が3つ以下にできることを証明してください。

また、一般に○個の要素を持つ集合から×要素数の部分集合を○個取り出すとき、Mの最小値が3になるための○と×の条件はどのようになるでしょうか。