次: 参考書 上: ラムゼー型定理 前: 漸化不等式

エルディシュ問題

太郎　 下限の確定が難しいということですが，2014年の次の問題では，上限と下限が一致しました． 次のは青空学園の解答です．

例題 0.2   [2014早稲田教育4番]

     2個以上の正の整数を要素とする有限集合を$A$とする．

$A$のどの2数も一方が他方を割り切るとき$A$は良い集合であるといい，$A$のどの2数も互いに他を割り切らないとき$A$は悪い集合であるという．

また，$A$の良い部分集合の要素の個数の最大値，すなわち，

$$\max \{n(B)\ \vert\ B \subset A,\ n(B)\ge 2\ かつ\ Bは良い集合\}$$

を$A$の最良数と定義し，$A$の悪い部分集合の要素の個数の最大値，すなわち，

$$\max \{n(B)\ \vert\ B \subset A,\ n(B)\ge 2\ かつ\ Bは悪い集合\}$$

を$A$の最悪数と定義する．

たとえば， $A=\{2,\ 3,\ 5,\ 7,\ 11,\ 14,\ 15,\ 77,\ 154,\ 225,\ 231,\ 308\}$のとき， $A$の良い部分集合は $\{7,\ 77,\ 231\}$， $\{7,\ 14,\ 154,\ 308\}$， $\{11,\ 77,\ 154,\ 308\}$などであり，$A$の最良数は4である． また，$A$の悪い部分集合は $\{231,\ 308\}$， $\{14,\ 15,\ 77\}$， $\{2,\ 7,\ 11,\ 15\}$， $\{2,\ 3,\ 5,\ 7,\ 11\}$などであり，$A$の最悪数は5である．

$k$を2以上の整数とするとき，次の問いに答えよ．

1. $n(A)=k^2$で，かつ最良数も最悪数も$k$である集合$A$が存在することを証明せよ．
2. $n(A)=k^2+1$ならば， $A$の最良数または$A$の最悪数のどちらかは$k+1$以上であることを証明せよ．
3. 要素数が2014で，かつ最良数と最悪数が等しいような集合，すなわち，
   
   $$n(A)＝2014\ かつ（Aの最良数）=（Aの最悪数）$$
   
   を満たす集合$A$を考える．このような集合たちの中で最良数が最小となる集合の例を挙げよ．

解答

1. 奇数の素数は無限個ある．相異なる奇数の素数を$k$個選びそれを $p_l,\ p_2,\ \cdots,\ p_k$とする．このとき$A$を
   
   $$A=\{2^ip_j\ \vert\ 0\le i \le k-1,\ 1\le l \le k\}$$
   
   で定める．$n(A)=k^2$である． $2^{i_1}p_{j_1}$と $2^{i_2}p_{j_2}$は，$j_1=j_2$なら一方が他方を割り切り， $j_1\ne j_2$なら互いに他方を割り切らない． $j_1$や$i_1$を固定し
   $$\begin{eqnarray*} &&B=\{2^ip_{j_1}\ \vert\ 0\le i \le k-1\}\\ &&C=\{2^{i_1}p_j\ \vert\ 1\le j \le k\} \end{eqnarray*}$$
   
   とおく．それぞれ要素の個数は$k$である．

   このとき，$B$は良い集合である． また$k+1$個以上の要素からなる部分集合には， 素数部分が相異なる2数が含まれる． その2数は互いに他方を割り切らない． よつて$k+1$個以上の要素からなる良い部分集合は存在しない．

   このとき，$C$は悪い集合である． また$k+1$個以上の要素からなる部分集合には，素数部分が等しい2数が含まれる． その2数は一方が他方を割り切る． よって$k+1$個以上の要素からなる悪い部分集合は存在しない．

   これから$A$は最良数も最悪数も$k$となる集合である．

2. $A$の要素$a$に対し，$l(a)$を，$a$を最小の要素として含む良い集合のなかで， 要素の個数が最大のもののその個数とする．つまり
   
   $$l(a)=\max \{n(B)\ \vert\ a\in B,\ b\in B\Rightarrow a\le b\ ,\ Bは良い集合\}$$
   
   そして $S(k)=\{a\ \vert\ l(a)=k\}$とおく．

   $S(k)$は悪い集合である． なぜなら，もし$S(k)$の2要素$a$と$b$で$a$が$b$を割るものがあれば $l(a)>l(b)$となるからである．

   $A$の部分集合
   

   $$S(1)\cup S(2)\cup \cdots\cup S(k)$$
   
   を考える．$A$の要素でこの部分集合に入らないものがあれば， それを最小の要素として含む良い集合は$k+1$以上の要素からなり， 最良数は$k+1$以上である．

   $A$のすべての要素がこのうちのいずれかに入れば，$n(A)=k^2+1$なので， どれかは$k+1$以上の要素からなる． つまり$k+1$個以上からなる悪い集合が存在し，最悪数が$k+1$以上となる．

3. 
   
   $$44^2=1936<2014<45^2=2025$$
   
   である．

   最良数と最悪数が等しいとき，その個数を$m$と置くと，(2)の議論から
   

   $$N(A)\le m^2$$
   
   この結果
   
   $$44<m$$
   
   が必要である．

   $m=45$で$n(A)=2014$となるものを構成すれば，それが例になる．

   (1)で$k=45$として構成した集合を$A'$とする． $A'$の部分集合$B$を
   

   $$B=\{p_l,\ p_2,\ \cdots,\ p_{45},\ 2p_1,\ \cdots,\ 2^44p_1\}$$
   
   とする．これは89個の要素からなる．この部分集合
   $$\begin{eqnarray*} B_1&=&\{p_l,\ p_2,\ \cdots,\ p_{45}\}\\ B_2&=&\{p_l,\ 2p_1,\ \cdots,\ 2^44p_1\} \end{eqnarray*}$$
   
   がそれぞれ最悪数と最良数45を与える．

   集合$A'-B$から任意に，要素の個数が$2014-89=1925$の部分集合$C$を選ぶ． $C$の良い集合や悪い集合の要素の個数は45を超えず， また$C$のどの要素を$B_1$や$B_2$に加えても，それぞれ最悪数や最良数を増やすことはない．

   よって$A=B\cup C$とすると，
   

   $$n(A)=2014,\ かつ最悪数=最良数=45$$
   
   である集合$A$が構成された． □

(2)の別解      $A$のすべての要素を次の原則を満たすように，上下に並ぶ平行な直線上に配置する．

(i)

倍数を上段に置き，割る数と割られる数を結ぶ．

(ii)

割る数と割られる数が隣りあう平行線上に置けるときは置く．

(iii)

結びあう数がないものは最下段に置く．

たとえば本問の$A$は次のようになる．

原則(ii)によって，最下段から最上段の数まで一段ずつ数のある折れ線が存在する． よって段数が最良数である．

また同じ段にある数は，互いに他方を割り切らず，その集合は悪い部分集合である． その要素の個数は最悪数を超えない．

$n(A)$は各段の要素の個数を加えたものであるから

$$n(A)\le (最悪数)\times(最良数)$$

である．

$n(A)=k^2+1$のとき，

$$最悪数 \le k\ かつ\ 最良数 \le k$$

と仮定すると，$k^2+1\le k^2$となり，矛盾する．

よって$A$の最悪数と最良数の少なくとも一方は$k+1$以上である． □

太郎　 そういえば，上限が同様な数となる例題を見たことがあります．

例題 0.3        1から$50$までのカードが1枚ずつある． これらのカードを1列に並べ，それを

$$a_1,\ a_2,\ \cdots,\ a_{50}$$

とする．ここから$8$枚のカードを抜き出し順序を変えずに

$$b_1,\ b_2,\ \cdots,\ b_8$$

とする．このとき$50$枚のカードをどのように並べても，かならず

$$b_1<b_2<\cdots<b_8\quad または\quad b_1>b_2>\cdots>b_8$$

となるものが選び出せることを示せ．

解答      並べられた50枚のカード

$$a_1,\ a_2,\ \cdots,\ a_{50}$$

の各々に次のように数の組$(i,\ j)$を対応させる．

$a_k$からはじまって右方に伸びる増加列の最大長を$i$， 減少列の最大長を$j$とする．このときカード$a_k$に$(i,\ j)$を対応させる．

$k\ne l$のとき，$a_k$に対応する$(i,\ j)$と，$a_l$に対応する$(s,\ t)$は異なる． なぜなら，$a_k<a_l$なら$i>s$であるし，$a_k>a_l$なら$j>t$であるからである．

そこで， このとき$50$枚のカードのどのような並べ方に対しても，

$$b_1<b_2<\cdots<b_8\quad または\quad b_1>b_2>\cdots>b_8$$

となるものが選び出せなかったとする． この場合，最大長が7以下なので50枚のカードに対応させた数の組 $(i,\ j)$に現れる$i$も$j$もすべて7以下であるということを意味する．

ところがこのような数の組は$7\cdot7=49$組しかない． したがって50枚のカードに対応させた数の組には少なくとも1組同じものがなければならない．

これは $k\ne l$のとき，$a_k$に対応する$(i,\ j)$と，$a_l$に対応する$(s,\ t)$は異なる， という結果と矛盾する．

したがって背理法によって題意が示された． □

太郎　 この50と8の関係が$(81)^2+1=50$で 8の代わりに$n$にして，50を$(n-1)^2+1$にしても，まったく同様に示せます．

2014年の早稲田の問題を参考に知ると，次の別解ができました． 一般の場合でやってみます．

別解      カード$a_i$に対し，$l_i$を，$a_i$から始まる増加列で最長のものの長さとする． そして $S(k)=\{a_i\ \vert\ l_i=k\}$とおく．

$S(k)$は減少列である． なぜなら，もし$S(k)$の2要素$a_s$と$a_t$で$a_s<a_t$となるものがあれば $l_s>l_t$となるからである．

集合

$$S(1)\cup S(2)\cup \cdots\cup S(n-1)$$

を考える．$\{a_i\}$でこの集合に入らないものがあれば， それから始まる増加列は$n$以上である．

$\{a_i\}$がすべてこの集合に入れば， $S(1),\ S(2),\ \cdots,\ S(n-1)$のどれかは$n$以上の要素からなる． もしすべて$n-1$以下なら総数が高々$(n-1)^2$だからである． よって総数が$(n-1)^2+1$なら，$n$個以上からなる減少列が存在する． □

南海　 これはよく考えている．

太郎　 この2つは同じ問題でしょうか．

南海　 まず，例題0.3はErdös-Szekeres（エルディシュ-ゼッカーズ）の定理といわれる美しい定理である． この語で検索してみると，さまざまの証明法などもある． また，これは離散幾何といわれる分野に関わる． これについてもここでは宿題にしておこう．

その上で，例題0.3と例題0.3は異なる． 例題0.3では，集合の中に2つの関係が入っている．$a<b$か$a>b$である．そして一方の否定が他方になる． この2つの関係は，いずれも順序の関係を満たす．

$$a<b,\ b<c\ \Rightarrow a<c\quad ,\ a>b,\ b>c\ \Rightarrow a>c$$

が成り立つ．

太郎　 そうか．例題0.3では，「$a$は$b$の倍数である」という関係は順序の関係を満たすが その否定「$a$は$b$の倍数でない」は順序の関係は満たさない． だから例題0.3を，数の組$(i,\ j)$を考えることで示すことはできないのです．

南海　 そういうことだ．さらに，一般の$n$についてErdös-Szekeresの定理でいう増加列や減少列が存在するための必要条件は確定していないはずだ．最近の結果までは確認できないが，たいへん難しい問題であることまちがいない．

太郎　 例題0.3は，論理的に導いた上限が下限でもあるという，その意味ではまれな場合なのですね．

南海　 こういう離散数学は，日本の高校ではあまり重視されない分野であるのだが， 2014年の入試問題もあり，その背後に広がる分野について対話できたことは，意味があった．

次: 参考書 上: ラムゼー型定理 前: 漸化不等式