　一般に $10^7$ を $n$ とおく. $[i,j]$ で $i$ 行目 $j$ 列目のマスを表し, $s(a,b,j)$ で $[a,j]$ と $[b,j+1]$ の中心を結ぶ線分を表す. この形式で表される線分の全体を $T$ とし, 写像 $f:T\to \lbrace 0,1\rbrace$ を以下で定める.
$$f(t)= \begin{cases} 1 & (t\text{と}\ell\  \text{が共有点を持つとき})\\\\ 0 & (\text{otherwise}) \end{cases}$$
このとき, 求める値は以下で与えられる. すなわち $T$ の元 $n^3$ 個のうち, $f(t)=0$ なるものを数えればよい.
$$\frac{1}{n^{n+1}}\left(n^{n-1}\times\sum_{t\in T}f(t)\right)=\frac{1}{n^2}\sum_{t\in T}f(t)$$
　さらに $[i,j]$ の中心が $\ell$ の下側にあるような $i=1,2,\cdots,n$ の個数を $g(j)$ とおけば, $f(t)=0$ なる $t$ の個数は対称性より以下で与えられることがわかる.
$$2\sum_{j=1}^{n}g(j)g(j+1)$$
　ここで適当に座標を設定すれば, $\ell$ の式が $nx-(n+1)y=0$ で, その両端点が $(0,0),(n+1,n)$ であるとしてよい. このとき $[i,j]$ の中心は $(j-1\/2,i-1\/2)$ であるから, $g(j)$ は天井記号によって以下で表される.
$$g(j)=\left\lceil\frac{n}{n+1}\left(j-\frac{1}{2}\right)+\frac{1}{2}\right\rceil-1$$
明らかに $g(j+1)\leq g(j)+1$ より, $g(1)=0,g(n+1)=n$ と併せて $g(j)=j-1$ がわかる. したがって
$$2\sum_{j=1}^{n}g(j)g(j+1) = 2\sum_{j=1}^{n}j(j-1) = \frac{2}{3}(n-1)n(n+1)$$
よって求める平均値は以下で与えられ, 特に $n=10^7$ のとき解答すべき値は $\textbf{16666671666667}$ である.
$$\frac{1}{n^2}\left(n^3-\frac{2}{3}(n-1)n(n+1)\right)=\frac{n^2+2}{3n}$$
公式解説
https://onlinemathcontest.com/contests/omc026/editorial/158
　$10^7$ 行 $10^7+1$ 列のマス目があり, 最も左下の頂点と最も右上の頂点を結ぶ直線を
$\ell$ とします. いま, 各列についてちょうど $1$ マスを黒く塗り, 隣り合う列の黒いマスの中心を線分で結ぶことで折れ線 $\ell^{\prime}$ を作ります. このとき, すべての黒マスの塗り方 $10^{7(10^7+1)}$ 通りについて, $\ell$ と $\ell^{\prime}$ の共有点の個数の平均を求めてください.\
　ただし, 答えは互いに素な正整数 $p,q$ によって $\dfrac{p}{q}$ と表せるので, $p+q$ を解答してください.\
　ここで, マスはすべて正方形とし, 各マスの**中心**を正方形の対角線の交点として定めます.