解説

方針・初手

点は $y=0$ 上と $y=1$ 上の2本の直線上に並んでいる。3点がすべて同じ直線上にあると三角形にならないため、面積が正になるのは「一方の直線上から2点、もう一方の直線上から1点」を選ぶ場合である。

このとき、高さは常に $1$ なので、面積は同じ直線上にある2点の $x$ 座標の差だけで決まる。

解法1

$y=0$ 上の点を

$$ (0,0),(1,0),\ldots,(n,0)

$$

$y=1$ 上の点を

$$ (0,1),(1,1),\ldots,(n,1)

$$

とする。

まず、$y=0$ 上から2点、$y=1$ 上から1点を選ぶ場合を考える。

$y=0$ 上の2点を $(i,0),(j,0)$ とし、$0 \leq i < j \leq n$ とする。この2点を底辺とすれば、底辺の長さは $j-i$、高さは $1$ であるから、面積は

$$ \frac{j-i}{2}

$$

である。

このとき、$y=1$ 上の1点は $n+1$ 通りに選べる。したがって、$y=0$ 上から2点、$y=1$ 上から1点を選ぶ三角形の面積の総和は

$$ (n+1)\sum_{0\leq i<j\leq n}\frac{j-i}{2}

$$

である。

同様に、$y=1$ 上から2点、$y=0$ 上から1点を選ぶ場合もまったく同じ総和になる。

よって、求める総和は

$$ 2\cdot (n+1)\sum_{0\leq i<j\leq n}\frac{j-i}{2}

$$

である。したがって

$$ (n+1)\sum_{0\leq i<j\leq n}(j-i)

$$

を計算すればよい。

ここで、差 $j-i$ が $d$ である組 $(i,j)$ の個数は、$d=1,2,\ldots,n$ に対して $n+1-d$ 個である。よって

$$ \begin{aligned} \sum_{0\leq i<j\leq n}(j-i) &= \sum_{d=1}^{n}d(n+1-d) \end{aligned} $$

となる。これを計算すると

$$ \begin{aligned} \sum_{d=1}^{n}d(n+1-d) &=(n+1)\sum_{d=1}^{n}d-\sum_{d=1}^{n}d^2 \\ &=(n+1)\cdot \frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6} \\ &=\frac{n(n+1){3(n+1)-(2n+1)}}{6} \\ &=\frac{n(n+1)(n+2)}{6} \end{aligned}

$$

である。

したがって、面積の総和は

$$ \begin{aligned} (n+1)\cdot \frac{n(n+1)(n+2)}{6} &= \frac{n(n+1)^2(n+2)}{6} \end{aligned} $$

である。

解説

この問題では、3点の選び方を直接数えようとすると煩雑になる。重要なのは、すべての点が $y=0$ または $y=1$ 上にあるため、三角形の高さが常に $1$ になることである。

したがって、面積は「同じ水平線上に選ばれた2点の距離」に比例する。あとは、$0,1,\ldots,n$ から2つ選んだときの差の総和

$$ \sum_{0\leq i<j\leq n}(j-i)

$$

を求める問題に帰着される。

差が $d$ になる組が $n+1-d$ 個ある、という数え方がこの問題の中心である。

答え

$$ \frac{n(n+1)^2(n+2)}{6}

$$