大阪大学 2001年 理系 第3問 解説

方針・初手

（1） は、円周上の点の間隔と線分の長さの関係を定式化する。円の中心と2点からなる三角形に着目し、余弦定理を用いて条件を三角関数の不等式に帰着させるのが自然である。

（2） は、（1） の結果を利用する。すべての辺が $\sqrt{2}$ 以上になることは、円周上の3点がそれぞれ「一定以上の間隔」を持って配置されることと同値である。間隔を文字で置き、方程式の非負整数解の個数に帰着させる方針と、1つの頂点を固定して条件を満たす残りの2点の選び方を数え上げる方針が考えられる。

解法1

(1)

円の中心を $O$ とする。半径 $1$ の円周上に $4n$ 個の点が等間隔に並んでいるため、隣り合う2点のなす中心角は $\frac{2\pi}{4n} = \frac{\pi}{2n}$ である。

点 $P_0$ と $P_k$ ($0 \le k \le 4n-1$) のなす中心角は $\angle P_0 O P_k = \frac{k\pi}{2n}$ と表せる。 $\triangle P_0 O P_k$ において余弦定理を用いると、線分 $P_0 P_k$ の長さの2乗は次のように計算できる。

$$ P_0 P_k^2 = 1^2 + 1^2 - 2 \cdot 1 \cdot 1 \cos \left( \frac{k\pi}{2n} \right) = 2 - 2\cos \frac{k\pi}{2n} $$

条件 $P_0 P_k \ge \sqrt{2}$ は $P_0 P_k^2 \ge 2$ と同値であるから、これを解く。

$$ \begin{aligned} 2 - 2\cos \frac{k\pi}{2n} &\ge 2 \\ \cos \frac{k\pi}{2n} &\le 0 \end{aligned} $$

$0 \le k \le 4n-1$ より、中心角の取り得る範囲は $0 \le \frac{k\pi}{2n} < 2\pi$ である。この範囲でコサインが $0$ 以下となる条件は以下の通りである。

$$ \frac{\pi}{2} \le \frac{k\pi}{2n} \le \frac{3\pi}{2} $$

各辺に $\frac{2n}{\pi}$ を掛けて整理すると、求める $k$ の範囲が得られる。

$$ n \le k \le 3n $$

(2)

（1） の結果から、円周上の2点を結ぶ線分の長さが $\sqrt{2}$ 以上となる条件は、その2点間の円周に沿った間隔（隣り合う点の間隔を $1$ としたときの弧の長さ）が $n$ 以上 $3n$ 以下であることである。

三角形の3頂点を円周に沿って反時計回りに選び、それぞれの頂点間の間隔を $x, y, z$ とする。 全体の点の数は $4n$ 個であるから、$x + y + z = 4n$ が成り立つ。 3辺の長さがすべて $\sqrt{2}$ 以上となるためには、各間隔が $n$ 以上であればよい。 （$x \ge n, y \ge n$ ならば $z = 4n - (x+y) \le 4n - 2n = 2n \le 3n$ となり、間隔が $3n$ 以下という条件は自動的に満たされる。）

したがって、満たすべき条件は $x, y, z$ が自然数であり、かつ以下の連立方程式・不等式を満たすことである。

$$ \begin{cases} x + y + z = 4n \\ x \ge n, \ y \ge n, \ z \ge n \end{cases} $$

ここで、$X = x - n, Y = y - n, Z = z - n$ とおくと、$X, Y, Z$ は $0$ 以上の整数となり、条件式は次のように書き換えられる。

$$ X + Y + Z = (x - n) + (y - n) + (z - n) = 4n - 3n = n $$

これを満たす $0$ 以上の整数 $(X, Y, Z)$ の組の個数は、異なる3種類のものから重複を許して $n$ 個選ぶ重複組合せの総数に等しい。

$$ {}_3\text{H}_n = {}_{n+3-1}\text{C}_n = {}_{n+2}\text{C}_2 = \frac{(n+2)(n+1)}{2} $$

次に、円周上の $4n$ 個の点から起点となる第1の頂点を選ぶ。その選び方は $4n$ 通りである。 この頂点を固定したとき、反時計回りに間隔が $x, y, z$ となるように第2、第3の頂点を定める方法が $\frac{(n+2)(n+1)}{2}$ 通りある。 これを掛け合わせると、条件を満たす三角形の順列の総数が得られる。

$$ 4n \times \frac{(n+2)(n+1)}{2} = 2n(n+1)(n+2) $$

しかし、1つの三角形に着目したとき、その3つの頂点のいずれを「起点となる第1の頂点」として選ぶかによって、1つの三角形につきちょうど3回ずつ重複して数えられている。 したがって、求める三角形の個数 $g(n)$ はこれを $3$ で割ることで得られる。

$$ g(n) = \frac{2n(n+1)(n+2)}{3} $$

解法2

（1） は解法1と同様。

(2)

特定の頂点を固定し、条件を満たす三角形の個数を直接数え上げる。 まず、頂点 $P_0$ を1つの頂点とする三角形について考える。 残りの2頂点を $P_a, P_b$ ($0 < a < b < 4n$) とすると、3辺の長さがすべて $\sqrt{2}$ 以上になるためには、（1） の結果から各頂点間の間隔がすべて $n$ 以上であればよい。 したがって、$a, b$ が満たすべき条件は以下のようになる。

$$ \begin{cases} a \ge n \\ b - a \ge n \\ 4n - b \ge n \end{cases} $$

これを $b$ について整理すると、以下の不等式が得られる。

$$ a + n \le b \le 3n $$

このような整数 $b$ が存在するためには、$a + n \le 3n$ すなわち $a \le 2n$ でなければならない。最初の条件 $a \ge n$ と合わせて、$a$ の取り得る範囲は以下のようになる。

$$ n \le a \le 2n $$

ある $a$ を固定したとき、条件を満たす $b$ の個数は、不等式を満たす整数の個数であるから、

$$ 3n - (a + n) + 1 = 2n - a + 1 $$

となる。これを $a = n$ から $2n$ まで足し合わせることで、$P_0$ を頂点に持つ条件を満たす三角形の個数が求められる。

$$ \sum_{a=n}^{2n} (2n - a + 1) $$

$a$ が $n$ から $2n$ まで変化するとき、$(2n - a + 1)$ の値は $n+1, n, n-1, \cdots, 1$ と減少していく。これは初項 $1$、末項 $n+1$、項数 $n+1$ の等差数列の和に等しいため、その和は次のように計算できる。

$$ \frac{1}{2}(n+1)\{1 + (n+1)\} = \frac{(n+1)(n+2)}{2} $$

対称性より、任意の頂点 $P_i$ ($0 \le i \le 4n-1$) について、それを頂点に持つ条件を満たす三角形の個数も等しく $\frac{(n+1)(n+2)}{2}$ 個である。 これを $4n$ 個すべての頂点について足し合わせると、

$$ 4n \times \frac{(n+1)(n+2)}{2} = 2n(n+1)(n+2) $$

となる。 1つの三角形には3つの頂点があるため、すべての頂点について足し合わせるこの計算では、1つの三角形につき3回ずつ重複して数えていることになる。 したがって、求める三角形の個数 $g(n)$ は、総和を $3$ で割って求められる。

$$ g(n) = \frac{2n(n+1)(n+2)}{3} $$

解説

円周上の点の配置と多角形の条件を組み合わせた典型的な整数問題である。 （1） で辺の長さを「円周上の間隔」という離散的な値に翻訳できたかが第一の関門である。 （2） は、場合の数の処理において「対称性を利用して全体を足し合わせ、重複度で割る」という手法が非常に有効である。 解法1のように間隔を変数 $x, y, z$ に置き換えて方程式の整数解の個数に帰着させる方法は、数え落としや重複計算を防ぎやすい強力なアプローチである。解法2のように1点を固定してシグマ計算を行う方法も直接的で自然であるが、変数の範囲の取り扱いに注意が必要となる。いずれの解法でも、最後に重複度 $3$ で割ることを忘れないようにしたい。

答え

(1)

$n \le k \le 3n$

(2)

$g(n) = \frac{2n(n+1)(n+2)}{3}$