IV慶應義塾大学 2004年 数学 第IV問解答・解説

設問(1)から(4)に答えなさい。　 $n$ を2以上の自然数とし，$2n$ 個の点 $P_{1},P_{2},\ldots,P_{2n}$ が同一円周上の異なる位置にある。これらの点のうちの2点を両端とする線分が $m$ 本あり，さらに $m\geq3$ のとき，次の条件(A)が満たされていると仮定する。　 (A) これらの線分のうちのどの3本も（点 $P_{1},\ldots,P_{2n}$ のうちの任意の3点を頂点とするような）三角形を形づくることはない。　 異なる2点 $P_{i}$ と $P_{j}$ を結ぶ線分があるとき $x_{ij}=x_{ji}=1$，そうでないとき $x_{ij}=x_{ji}=0$ とし， $$\displaystyle a_{i}=\sum\limits _{j=1}^{2n}x_{ij},\qquad b_{ij}=\sum\limits _{k=1}^{2n}x_{ik}x_{jk}\quad(\text{ただし }x_{ii}=0)$$ とおくと，$\displaystyle \sum\limits _{i=1}^{2n}a_{i}=\boxed{(\text{あ})}\times m$ となる。条件(A)より，任意の $i,j\ (i=j\text{の場合も含む})$ に対して $$b_{ij}\leq(1-x_{ij})a_{i}\qquad\cdots\cdots(1)$$ が成り立つ。さらに，任意の実数 $t$ に対して $\displaystyle \sum\limits _{k=1}^{2n}(ta_{k}+1)^{2}\geq0$ が成り立つことと $$\displaystyle \sum\limits _{i=1}^{2n}\sum\limits _{j=1}^{2n}b_{ij} =\sum\limits _{i=1}^{2n}\sum\limits _{j=1}^{2n}\left(\sum\limits _{k=1}^{2n}x_{ik}x_{jk}\right) =\sum\limits _{k=1}^{2n}\left(\sum\limits _{i=1}^{2n}x_{ik}\right)\left(\sum\limits _{j=1}^{2n}x_{jk}\right) =\sum\limits _{k=1}^{2n}a_{k}^{2}\qquad\cdots\cdots(2)$$ を用いると $$m\leq n^{2}\qquad\cdots(3)$$ が示される。ただし，一般に $N^{2}$ 個の数 $c_{ij}\ (1\leq i\leq N,\ 1\leq j\leq N)$ に対して $$\displaystyle \sum\limits _{i=1}^{N}\left(\sum\limits _{j=1}^{N}c_{ij}\right)=\sum\limits _{j=1}^{N}\left(\sum\limits _{i=1}^{N}c_{ij}\right)$$ であるので，括弧を省略して，この和を $\displaystyle \sum\limits _{i=1}^{N}\sum\limits _{j=1}^{N}c_{ij}$ と書く。いま，(3)の等号が成り立っている場合を考える。点 $P_{2n}$ と線分で結ばれているのは点 $P_{1},P_{2},\ldots,P_{r}$ のみであるとすると，$r=\boxed{(\text{い})}$ でなければならない。このとき，点 $P_{2n-1}$ と線分で結ばれているのは点 $\boxed{(\text{う})}$ のみである。

(1) $(\text{あ})$ に適切な数を入れなさい。

(2) (1)を証明しなさい。

(3) (3)を証明しなさい。(2)は証明なしで用いてよい。

(4) $(\text{い})$ に適切な数または式を，$(\text{う})$ に適切な点の列を入れなさい。