OMC174(E)

　一般に $\mathcal P$ を凸 $2n$ 角形として考える．相異なる $2$ 頂点を結ぶ線分の長さを，$2$ 点の間にある辺の本数（のうち大きくない方）と定義する．
　着色された線分の長さが奇数ならば，必ず偶数本の着色された線分と交わり，長さが偶数ならば，必ず奇数本の着色された線分と交わる．よって，この問題では，長さが偶数の着色された線分同士の交点の個数の（相加）平均を求めればよい．
　着色する $n$ 本の選び方すべてについて，長さが偶数の着色された線分同士の交点の個数の総和を $S_n$ とおく．（着色の有無によらない）長さが偶数の線分同士のある交点に着目するとき，この点が「長さが偶数の着色された線分同士の交点」として計上され $S_n$ に寄与する回数は，この点を通る線分以外の $n-2$ 本の選び方の場合の数 $$\dbinom{2n-4}{2}\dbinom{2n-6}{2}\cdots\dbinom{2}{2}\times\dfrac{1}{(n-2)!}=\dfrac{(2n-4)!}{2^{n-2}(n-2)!}\quad\cdots(1)$$ に等しい．（着色の有無によらない）長さが偶数の線分同士の交点の個数は，$2n$ 個の頂点から相異なる $4$ 点を選ぶとき，隣り合う点の間にある辺の本数が (i) すべて偶数である場合の数と (ii) すべて奇数である場合の数の和に等しい．

• (i) は，$1\leq a\lt b\lt c\lt d\leq 2n$ をみたし，すべての偶奇が一致する整数の組 $(a, b, c, d)$ の数に等しい．
• (ii) は，$1\leq a\lt b\lt c\lt d\leq 2n$ をみたし，偶数と奇数が互い違いに並ぶ $(a, b, c, d)$ の数に等しい．これは，$1\leq a\lt b+1\lt c+2\lt d+3\leq 2n+3$ をみたし，すべての偶奇が一致する $(a, b+1, c+2, d+3)$ の数に等しい．

したがって，（着色の有無によらない）長さが偶数の線分同士の交点の個数は， $$\dbinom{n}{4}\times2+\dbinom{n+2}{4}+\dbinom{n+1}{4}=\dfrac{1}{6}(n-1)n(n^2-2n+3)\quad\cdots(2)$$ 　$S_n$ は (1), (2) の積である．また，着色する $n$ 本の選び方の総数は， $$\dbinom{2n}{2}\dbinom{2n-2}{2}\cdots\dbinom{2}{2}\times\dfrac{1}{n!}=\dfrac{(2n)!}{2^{n}n!}$$ であるから，求める平均値は， $$S_n\times\dfrac{2^{n}n!}{(2n)!}=\dfrac{(n-1)n(n^2-2n+3)}{6(2n-1)(2n-3)}$$ とわかる．$n=100$ を代入すれば，（分母と分子が $6$ で割り切れることに注意して）特に解答すべき値 $\bm{16214153}$ を得る．