二項係数と数学オリンピック2025 第11問（JMO）

星の名前の定義

帰納的に，$f:X \to Y$ から得られる $S_f$ に $XY$ という名前を対応づける。

このとき，星 $X$ の重要度は $X$ に現れる $O$ 以外の文字の個数に対応する。

星と航路の対応

次に $n$ 回目の操作の後にできた星と直行便について次が従うことを示す。

(a)：星 $X$ は，元の航路において $n$ 回移動した経路（$n+1$ 個の星を移動したもの）に対応する。（対応する経路を $X_0 \to X_1 \to \cdots \to X_n$ と書く。）

(b)：星 $X$ と星 $Y$ の間に直行便があることと，対応する経路について $X_1 = Y_0 , \cdots , X_n = Y_{n-1}$ は同値である。

$n=1$ のときは実際に計算することで分かる。

$n=k$ で成立すると仮定する。$k$ 回の操作でできた星 $X$，星 $Y$ の間に直行便があるとする。このとき (b) より $XY$ は経路 $X_0 \to X_1 \to \cdots \to X_k \to Y_k$ に対応する。

$XY$ から直行便が存在する星を考える。問題の条件 (3) より，$XY$ から直行便が伸びる星は，$Y$ が始点となる直行便 $f'$ から建設される $S_{f'}$ に限る。

直行便 $f' : Y \to Z$ がある場合，(b) より $Y_2 = Z_1 , \cdots , Y_k = Z_{k-1}$ である。ゆえに 直行便 $XY \to YZ$ は経路 $X_0 \to X_1 \to \cdots \to X_k \to Y_k \to Z_k$ に対応する。

よって成立する。

経路から星の名前を定める

経路 $X_0 \to X_1 \to \cdots \to X_n$ から得られる星の名前に，$X_m \ (m = 0,1, \cdots , n)$ が現れる回数を $X(m)$ とする。このとき $X(k) = {}_n \mathrm{C}_k$ であることを示す。

$n$ に関する帰納法で示す。$n=1$ のときは既に計算した通りである。

$n=k$ で従うと仮定する。$X \to Y$ から得られる星 $XY$ について考える。$m=0,k+1$ のときはそれぞれ $XY(0) = X(0) = 1, XY(k+1) = Y(k) = 1$ である。

$m =1,2, \cdots , k$ のときを考える。$(XY)_m = X_m = Y_{m+1}$ である。よって $XY(m) = X(m) + Y(m+1)$ である。

帰納法の仮定から $X(m) = {}_k \mathrm{C}_m$，$Y(m+1) = {}_k \mathrm{C}_{m+1}$ であるため，二項係数の性質から $XY(m) = {}_{k+1} \mathrm{C}_m$ である。こうして示された。

経路の場合分け

元のグラフから，どのような経路においても3回に1度 $O$ を通過する。よって，$O$ が最初に登場する場所に応じて場合分けをすればよい。

航路の対称性から，まずは $O,A,B$ のみを通過する経路を考え，$A$ と $B$ をそれぞれ $C$ と $D$ に置き換えることにより，すべての経路を調べる。

出発点が $O$ である経路

経路は $$\underbrace{OABOAB \cdots OAB}_{33\ \text{セット}} OA$$ である。（矢印は省略した）

この経路に対応する星の重要度は $$0 \cdot {}_{100} \mathrm{C}_0 + 1 \cdot {}_{100} \mathrm{C}_1 + 1 \cdot {}_{100} \mathrm{C}_2 + \cdots + 0 \cdot {}_{100} \mathrm{C}_{99} + 1 \cdot {}_{100} \mathrm{C}_{100}$$ である。

同様に $O$ を出発点とする経路は，上の経路において $A$ が34回，$B$ が $33$ 回登場することから $2^{67}$ 個存在する。

1回目の移動で初めて $O$ が登場する経路

$O,A,B$ だけを通る場合，経路は $$\underbrace{BOABOA \cdots BOA}_{33\ \text{セット}} BO$$ である。（矢印は省略した）

この経路に対応する星の重要度は $$1 \cdot {}_{100} \mathrm{C}_0 + 0 \cdot {}_{100} \mathrm{C}_1 + 1 \cdot {}_{100} \mathrm{C}_2 + \cdots + 1 \cdot {}_{100} \mathrm{C}_{99} + 0 \cdot {}_{100} \mathrm{C}_{100}$$ である。

同様の経路は，上の経路において $A$ が33回，$B$ が $34$ 回登場することから $2^{67}$ 個存在する。

2回目の移動で初めて $O$ が登場する経路

$O,A,B$ だけを通る場合，経路は $$\underbrace{ABOABO \cdots ABO}_{33\ \text{セット}} AB$$ である。（矢印は省略した）

この経路に対応する星の重要度は $$1 \cdot {}_{100} \mathrm{C}_0 + 1 \cdot {}_{100} \mathrm{C}_1 + 0 \cdot {}_{100} \mathrm{C}_2 + \cdots + 1 \cdot {}_{100} \mathrm{C}_{99} + 1 \cdot {}_{100} \mathrm{C}_{100}$$ である。

同様の経路は，上の経路において $A$ が34回，$B$ が $34$ 回登場することから $2^{68}$ 個存在する。

重要度の総和

上記の計算により重要度の総和は $$\begin{aligned} & (0 \cdot {}_{100} \mathrm{C}_0 + 1 \cdot {}_{100} \mathrm{C}_1 + 1 \cdot {}_{100} \mathrm{C}_2 +\\ & \quad \cdots + 0 \cdot {}_{100} \mathrm{C}_{99} + 1 \cdot {}_{100} \mathrm{C}_{100}) \times 2^{67}\\ +& (1 \cdot {}_{100} \mathrm{C}_0 + 0 \cdot {}_{100} \mathrm{C}_1 + 1 \cdot {}_{100} \mathrm{C}_2 +\\ &\quad \cdots + 1 \cdot {}_{100} \mathrm{C}_{99} + 1 \cdot {}_{100} \mathrm{C}_{100}) \times 2^{67}\\ +& (1 \cdot {}_{100} \mathrm{C}_0 + 1 \cdot {}_{100} \mathrm{C}_1 + 0 \cdot {}_{100} \mathrm{C}_2 +\\ & \quad \cdots + 1 \cdot {}_{100} \mathrm{C}_{99} + 0 \cdot {}_{100} \mathrm{C}_{100}) \times 2^{68}\\ =& (1 \cdot {}_{100} \mathrm{C}_0 + 1 \cdot {}_{100} \mathrm{C}_1 + 1 \cdot {}_{100} \mathrm{C}_2 +\\ & \cdots + 1 \cdot {}_{100} \mathrm{C}_{99} + 1 \cdot {}_{100} \mathrm{C}_{100}) \times 3 \times 2^{67}\\ & - ({}_{100} \mathrm{C}_2 + {}_{100} \mathrm{C}_{5} + \cdots + {}_{100} \mathrm{C}_{98}) \times 2^{67}\\ =& \ 3 \times 2^{67} \times 2^{100} - ({}_{100} \mathrm{C}_2 + {}_{100} \mathrm{C}_{5} + \cdots + {}_{100} \mathrm{C}_{98}) \times 2^{67} \end{aligned}$$ である。

最後の項を計算する。ただし $\omega = \dfrac{-1+\sqrt{3}i}{2}$ とする。$\omega^3 = 1$ に注意すると， $$\begin{aligned} &({}_{100} \mathrm{C}_2 + {}_{100} \mathrm{C}_{5} + \cdots + {}_{100} \mathrm{C}_{98}) \times 3 \\ &= ({}_{100} \mathrm{C}_0 + {}_{100} \mathrm{C}_{3} + \cdots + {}_{100} \mathrm{C}_{99}) \times (\omega^2 + \omega + 1)\\ &\quad + ({}_{100} \mathrm{C}_1 + {}_{100} \mathrm{C}_{4} + \cdots + {}_{100} \mathrm{C}_{100}) \times (\omega^2 + \omega + 1)\\ &\quad + ({}_{100} \mathrm{C}_2 + {}_{100} \mathrm{C}_{5} + \cdots + {}_{100} \mathrm{C}_{98}) \times 3\\ &= ({}_{100} \mathrm{C}_0 + {}_{100} \mathrm{C}_{1} + \cdots + {}_{100} \mathrm{C}_{100})\\ &\quad + ({}_{100} \mathrm{C}_0 \omega^0 + {}_{100} \mathrm{C}_{1} \omega^1 + \cdots + {}_{100} \mathrm{C}_{100} \omega^{100}) \times \omega \\ &\quad + ({}_{100} \mathrm{C}_0 \omega^0 + {}_{100} \mathrm{C}_{1} \omega^2 + \cdots + {}_{100} \mathrm{C}_{100} \omega^{200}) \times \omega^2 \\ &= (1+1)^{100} + \omega (1+\omega)^{100} + \omega^2 (1+\omega^2)^{100} \end{aligned}$$ である。さらに $$\omega + 1 = \dfrac{1+\sqrt{3}i}{2} = \cos \dfrac{\pi}{3} + i \sin \dfrac{\pi}{3}\\ \omega^2 + 1 = \dfrac{1-\sqrt{3}i}{2} = \cos \dfrac{\pi}{3} + i \sin \dfrac{5\pi}{3}$$ より $$\begin{aligned} &(1+1)^{100} + \omega (1+\omega)^{100} + \omega^2 (1+\omega^2)^{100}\\ &= 2^{100} + \omega \left( \cos \dfrac{100}{3} \pi + i \sin \dfrac{100}{3} \pi \right)\\ &\qquad \qquad + \omega^2 \left( \cos \dfrac{200}{3} \pi + i \sin \dfrac{200}{3} \pi \right)\\ &= 2^{100} + \omega \left( \cos \dfrac{4}{3} \pi + i \sin \dfrac{4}{3} \pi \right)\\ &\qquad \qquad + \omega^2 \left( \cos \dfrac{2}{3} \pi + i \sin \dfrac{2}{3} \pi \right)\\ &= 2^{100}+2 \end{aligned}$$ である。

よって，重要度の総和は $$\begin{aligned} &3 \times 2^{67} \times 2^{100} - \dfrac{2^{100}+2}{3} \times 2^{67}\\ &= 2^{67} \times \dfrac{9 \times 2^{100}-2^{100}-2}{3}\\ &= 2^{67} \times \dfrac{8 \times 2^{100}-2}{3}\\ &= \dfrac{2^{68} (2^{102}-1)}{3} \end{aligned}$$ である。