2個以上の正の整数を要素とする有限集合をとする.
のどの2数も一方が他方を割り切るときは良い集合であるといい,のどの2数も互いに他を割り切らないときは悪い集合であるという.
また,の良い部分集合の要素の個数の最大値,すなわち,
たとえば, のとき, の良い部分集合は , , などであり,の最良数は4である. また,の悪い部分集合は , , , などであり,の最悪数は5である.
を2以上の整数とするとき,次の問いに答えよ.
解答
このとき,は良い集合である. また個以上の要素からなる部分集合には, 素数部分が相異なる2数が含まれる. その2数は互いに他方を割り切らない. よつて個以上の要素からなる良い部分集合は存在しない.
このとき,は悪い集合である. また個以上の要素からなる部分集合には,素数部分が等しい2数が含まれる. その2数は一方が他方を割り切る. よって個以上の要素からなる悪い部分集合は存在しない.
これからは最良数も最悪数もとなる集合である.
は悪い集合である. なぜなら,もしの2要素とでがを割るものがあれば となるからである.
の部分集合
のすべての要素がこのうちのいずれかに入れば,なので, どれかは以上の要素からなる. つまり個以上からなる悪い集合が存在し,最悪数が以上となる.
最良数と最悪数が等しいとき,その個数をと置くと,(2)の議論から
でとなるものを構成すれば,それが例になる.
(1)でとして構成した集合をとする.
の部分集合を
集合から任意に,要素の個数がの部分集合を選ぶ. の良い集合や悪い集合の要素の個数は45を超えず, またのどの要素をやに加えても,それぞれ最悪数や最良数を増やすことはない.
よってとすると,
(2)の別解 のすべての要素を次の原則を満たすように,上下に並ぶ平行な直線上に配置する.
たとえば本問のは次のようになる.
原則(ii)によって,最下段から最上段の数まで一段ずつ数のある折れ線が存在する. よって段数が最良数である.
また同じ段にある数は,互いに他方を割り切らず,その集合は悪い部分集合である. その要素の個数は最悪数を超えない.
は各段の要素の個数を加えたものであるから
のとき,
よっての最悪数と最良数の少なくとも一方は以上である. □
太郎 そういえば,上限が同様な数となる例題を見たことがあります.
解答
並べられた50枚のカード
からはじまって右方に伸びる増加列の最大長を, 減少列の最大長をとする.このときカードにを対応させる.
のとき,に対応すると,に対応するは異なる. なぜなら,ならであるし,ならであるからである.
そこで,
このとき枚のカードのどのような並べ方に対しても,
ところがこのような数の組は組しかない. したがって50枚のカードに対応させた数の組には少なくとも1組同じものがなければならない.
これは のとき,に対応すると,に対応するは異なる, という結果と矛盾する.
したがって背理法によって題意が示された. □
太郎
この50と8の関係がで
8の代わりににして,50をにしても,まったく同様に示せます.
2014年の早稲田の問題を参考に知ると,次の別解ができました. 一般の場合でやってみます.
別解 カードに対し,を,から始まる増加列で最長のものの長さとする. そして とおく.
は減少列である. なぜなら,もしの2要素とでとなるものがあれば となるからである.
集合
がすべてこの集合に入れば, のどれかは以上の要素からなる. もしすべて以下なら総数が高々だからである. よって総数がなら,個以上からなる減少列が存在する. □
南海 これはよく考えている.
太郎 この2つは同じ問題でしょうか.
南海 まず,例題0.3はErdös-Szekeres(エルディシュ-ゼッカーズ)の定理といわれる美しい定理である. この語で検索してみると,さまざまの証明法などもある. また,これは離散幾何といわれる分野に関わる. これについてもここでは宿題にしておこう.
その上で,例題0.3と例題0.3は異なる.
例題0.3では,集合の中に2つの関係が入っている.かである.そして一方の否定が他方になる.
この2つの関係は,いずれも順序の関係を満たす.
太郎 そうか.例題0.3では,「はの倍数である」という関係は順序の関係を満たすが その否定「はの倍数でない」は順序の関係は満たさない. だから例題0.3を,数の組を考えることで示すことはできないのです.
南海 そういうことだ.さらに,一般のについてErdös-Szekeresの定理でいう増加列や減少列が存在するための必要条件は確定していないはずだ.最近の結果までは確認できないが,たいへん難しい問題であることまちがいない.
太郎 例題0.3は,論理的に導いた上限が下限でもあるという,その意味ではまれな場合なのですね.
南海 こういう離散数学は,日本の高校ではあまり重視されない分野であるのだが, 2014年の入試問題もあり,その背後に広がる分野について対話できたことは,意味があった.