次: ラムゼー数 上: ラムゼー型定理

ある問題と一般化

太郎　 次のような問題に出会いました．鳩の巣原理を使う練習問題でした．

例題 0.1  

1. 6人の人がいる． どの2人も，互いに知り合いであるかまたは見ず知らずであるか，いずれかとする． すると，お互いに知り合いである3人がいるか， お互いに見ず知らずである3人がいるか，いずれかが成り立っていることを示せ．
2. 平面に17個の点がある．各2点は赤，青，黒のいずれかの線分で結ばれている． このとき3辺が同じ色の三角形が存在することを示せ．

解答

1. 6人を平面上の6点 $\mathrm{A}_0,\ \mathrm{A}_1,\ \cdots\ \mathrm{A}_5$に対応させる． 知り合いの場合は赤の線分で結び， 見ず知らずの場合は青の線分で結ぶ．

   点$\mathrm{A}_0$からは5本の線分が出ている．$5=2\cdot 2+1$なので赤か青かのいずれかは 3本以上である．赤が3本以上出ているとし，$\mathrm{A}_0$とそれらの線分で結ばれた点のうち の3点を $\mathrm{A}_1,\ \mathrm{A}_2,\ \mathrm{A}_3$とする． この3点を結ぶ3本の線分のなかに赤があるとする． それを $\mathrm{A}_1\mathrm{A}_2$とすると， 3点 $\mathrm{A}_0,\ \mathrm{A}_1,\ \mathrm{A}_2$に対応する3人は互いに知り合いである．

   $\mathrm{A}_1,\ \mathrm{A}_2,\ \mathrm{A}_3$を結ぶ3本の線分がすべて青とする．この場合， この3点に対応する3人は互いに見ず知らずである．

   赤青逆の場合も同様に示される．

   
2. 17個の点を $\mathrm{A}_0,\ \mathrm{A}_1,\ \cdots,\ \mathrm{A}_{16}$ で表す．これらの点が互いに青色，赤色，黒色の線分で結ばれている．

   点$\mathrm{A}_0$から出ている16本の線分を考える． $16=5\cdot3+1$なので，少なくともひとつの色については6本の線分が出ている．その色を 青とし，それらの端点を $\mathrm{A}_1,\ \mathrm{A}_2,\ \cdots,\ \mathrm{A}_6$とする．

   これら6個の点を結ぶ線分の中に青色があればその線分の両端の点と $\mathrm{A}_0$でできる三角形が題意を満たす．

   もしこれらの線分が赤色と黒色のみであったとする．

   この6点のうちには(1)により，赤か黒の三角形が少なくとも一つは存在する．

   したがって3辺が同じ色の三角形が存在することが示された．

太郎　 これを 有限個の点がある．各2点を定まった色で塗り分ける場合， 点がいくつあれば，3辺が同色の三角形がつねに存在すると言えるのか． という問題に一般化してみました． 色の数を$n$とし，次の漸化式で定まる数列$\{a_n\}$を考えました． 色が一色の場合，3点あればよいので，$a_1=3$とします．

定理 1        次の漸化式で数列$\{a_n\}$を定める．

$$a_1=3,\ a_{n+1}-1=(n+1)(a_n-1)+1$$

平面上に$a_n$個の点がある． 各2点をどのように$n$色で塗り分けても， つねに同色の三角形が存在する． ■

証明      $n$に関する数学的帰納法で示す． $n=1$のときは成立するので，$n$のとき$a_n$点あれば同色の3辺の三角形が存在するとする．

$a_{n+1}$個の点を $\mathrm{A}_0,\ \mathrm{A}_1,\ \cdots,\ \mathrm{A}_{a_{n+1}}$ で表す．これらの点が互いに色1，色2，…色$n$の線分で結ばれている．

点$\mathrm{A}_0$から出ている$a_{n+1}-1$本の線分を考える． $a_{n+1}-1=(n+1)(a_n-1)+1$なので，少なくともひとつの色については$a_n$本の線分が出ている． その色を色1とし，それらの端点を $\mathrm{A}_1,\ \mathrm{A}_2,\ \cdots,\ \mathrm{A}_{a_n}$とする．

これら$a_n$個の点を結ぶ線分の中に色1があればその線分の両端の点と $\mathrm{A}_0$でできる三角形が題意を満たす．

もしこれらの線分が色2〜色$n$であったとする． この$a_n$点のうちには帰納法の仮定によって，3辺が色2〜色$n$のいずれかの三角形が少なくとも一つは存在する．

したがって3辺が同じ色の三角形が存在することが示された． 　□

太郎　 この一般項は求まるのでしょうか．

南海　 このように問題を一般化してとらえようとすることは，大切なことだ．

次のようにすれば，$a_n$を書くことができる．

$$\dfrac{a_{n+1}-1}{(n+1)!}=\dfrac{a_n-1}{n!}+\dfrac{1}{(n+1)!}$$

と変形する．よって

$$\dfrac{a_n-1}{n!}=a_1-1+\dfrac{1}{2!}+\dfrac{1}{3!}+\cdots+\dfrac{1}{n!} =\sum_{k=0}^n\dfrac{1}{k!}$$

である．一方，$e$を自然対数の底とすると

$$e=\sum_{k=0}^{\infty}\dfrac{1}{k!}=\sum_{k=0}^{n}\dfrac{1}{k!}+\sum_{k=n+1}^{\infty}\dfrac{1}{k!}$$

であるが，ここで

$$\begin{eqnarray*} \sum_{k=n+1}^{\infty}\dfrac{1}{k!}&=&\dfrac{1}{(n+1)!} \left... ...1)!}\cdot\dfrac{1}{1-\dfrac{1}{n+2}} =\dfrac{n+2}{(n+1)!(n+1)} \end{eqnarray*}$$

よって

$$\dfrac{a_n-1}{n!}<e<\dfrac{a_n-1}{n!}+\dfrac{n+2}{(n+1)!(n+1)}$$

つまり

$$a_n-1<en!<a_n-1+\dfrac{n+2}{(n+1)!(n+1)}<a_n$$

この結果

$$en!<a_n<en!+1$$

$a_n$は正整数なので，

$$a_n=[en!+1]$$

と表される．ただし，実数$x$に対して$[x]$は$x$を超えない最大の整数を表す． 　□

太郎　 確かに

$$\begin{array}{l} a_1=[e+1]=3,\ a_2=[2e+1]=6,\ \\ a_3=... ...7\ (17.2=6\cdot 2.7+1<6e+1<6\cdot 2.72+1=17.32) \end{array}$$

です．

太郎　 色の数を一般化しましたが，さらに一般化はできるのでしょうか．

南海　

2点ずつ結んだ線分を$n$色で塗り分ける．

3点を選ぶとその3つの辺の色が同じである．

を

$r$個の点を結んだ多辺形を$n$色で塗り分ける．

$q$個の点を選ぶとそのうちの$r$個の点を結んだ多辺形はいずれも色が同じである．

とする．また集合$X$の各元を$n$色で塗り分けるとは， $X$から， $\{1,\ 2,\ \cdots,\ n\}$への写像を定めることに他ならない． さらに「$q$個の点」と言うところを，色によってその個数の指定を変えてもよい． つまり $i=1,\ 2,\ \cdots,\ n$に対して「$q_i$個の点」としたほうがより一般的になる．

その上で，先の問題を一般化すれば次のようになる．

集合$U$の$u$個の元からなるすべての部分集合の集合を$P(u\ ;\ U)$と表す．

定理 2       

$$q_k\ge r \ge 1\quad ,\ k=1,\ 2,\ \cdots,\ n$$

をみたす整数の組 $r,\ q_1,\ q_2,\ \cdots,\ q_n$を任意に定める． このとき，次の命題が成立する整数$R$が存在する．

命題：

$N$を$N\ge R$をみたす自然数とする． $N$個の元からなる集合$S$および $P(r\ ;\ S)$から $\{1,\ 2,\ \cdots,\ n\}$への任意の写像$\chi$に対し

$$V\in P(q_k\ ;\ S)\ かつ\ \chi(P(r\ ;\ V))=k$$

となる組$(V,\ k)$が存在する．

■

今後は，色の塗り分けで考えたり，写像$\chi$で考えたりするが， それは同じことである．

次: ラムゼー数 上: ラムゼー型定理