◆ 解説で用いる記号

• 計算量解析において、\(S = \sum_i |X_i|\) と書くことにします。

• 正の整数 \(K\) について、\(c = K\) の場合の数え上げ、つまり整数の組 \((a,b)\) のうちで以下が成り立つものの個数を \(g(K)\) と書くことにします。

  • \(0\leq a, b < K\)
  • 各 \(i\) に対して \(aX_i+b\) を \(K\) で割った余りを \(Y_i\) とするとき、\(Y_1 < Y_2 < \cdots < Y_N\) が成り立つ。

---

◆ \(f(K)\) と \(g(K)\) の関係

\(f(K) = \sum_{k=1}^K g(k)\) です。

後述のように、極限 \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\) が存在することを示すことができます。まずはこのことを認めて、問題の答を求めましょう。

正実数 \(\varepsilon > 0\) を任意にとります。 \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\) であるとき、十分大きなすべての \(K\) に対して \((c-\varepsilon)K^2 \leq g(K) \leq (c+\varepsilon)K^2\) が成り立ちます。このことから、十分大きなすべての \(K\) に対して \((c-2\varepsilon) \sum_{k=1}^Kk^2 \leq f(N) \leq (c+2\varepsilon)\sum_{k=1}^Kk^2 \) が成り立ちます。\(\sum_{k=1}^K k^2 = \frac13K^3 + O(K^2)\) なので、十分大きなすべての \(K\) に対して \((c-3\varepsilon)\cdot \frac13 K^3\leq f(K) \leq (c+3\varepsilon)\cdot \frac13 K^3\) が成り立ちます。

この式は \(\frac13 c - \varepsilon \leq \frac{f(K)}{K^3} \leq \frac13 c + \varepsilon\) と変形できます。任意の \(\varepsilon > 0\) に対して、十分大きな \(K\) がこの不等式を満たすことから、\(\lim_{K\to\infty}\frac{f(K)}{K^3} = \frac13 c\) であることが分かりました。

したがって、極限 \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\) の存在の仮定のもと、本問題の答が \(\frac13 c\) であることが示されました。

---

◆ 連続量による言い換え

\(Y_i = (aX_i + b)\bmod K\) が昇順に並ぶのはどういうときかを調べましょう。\(Y_i\) の代わりに \(Y_i / K\) を考えることにすると、調べるべきは \(\frac{a}{K}X_i + \frac{b}{K}\) の小数部分であると分かります。

実数 \(x\) に対して、その小数部分を \(\{x\}\) と書くことにします。つまり、\(\{x\} = x - \lfloor x\rfloor\) と書くことにします。

\(Y_i\) が昇順に並ぶことは、\(\{(a/K)X_i + (b/K)\}\) が昇順に並ぶことと言い換えられます。

そこで、\(\mathbb{R}^2\) の部分集合 \(D\) を、

\(D = \{(\alpha, \beta) \in [0,1]^2\mid \{\alpha X_1 + \beta\} < \{\alpha X_2 + \beta\} < \cdots\}\)

により定めます。

\(g(K)\) は、\((a/K, b/K) \in D\) となるような \(0\leq a,b <K\) の個数と言い換えられます。後述のように、\(D\) は有限個の線分により囲まれた図形の和集合になり、\(\lim_{K\to \infty} \frac{g(K)}{K^2}\) は、\(D\) の面積に一致することが証明できます。

答は \(D\) の面積の \(1/3\) 倍になります。そこで、\(D\) の面積を求める問題を考えることにします。

---

◆ \(D\) の計算

ぴったり \(\{\alpha X_i + \beta\} = \{\alpha X_{i+1} + \beta\}\) となるような \((\alpha, \beta)\) は \(D\) の面積には影響しないため、以下、このような場合の議論を無視します。

区間 \([0, 1)\) を \(0\) と \(1\) を貼り合わせることで、円周と見なし、\(\{\alpha X_i + \beta\}\) は円周上の点であると考えます。すると、\(\{\alpha X_i + \beta\}\) は \(\{\alpha X_i\}\) を正の向きに \(\beta\) 平行移動した点です。\(\{\alpha X_i + \beta\}\) が昇順であるとき、\(\{\alpha X_i\}\) も円周上のある位置から順に見ると \(i=1, 2, \ldots\) 順に並ぶことが分かります。まずは、このことが成り立つ \(\alpha\) の条件を調べます。

---

\(\{\alpha X_i\}\) が円周上に、ある位置から見て \(i=1, 2, \ldots\) の順に並ぶことは、任意の \(i\) に対して次が成り立つことと同値です：

• \(\{\alpha X_{i}\}\) から \(\{\alpha X_{i+1}\}\) までの正の向きの距離を \(f_i(\alpha)\) とするとき、\(\sum_{i=1}^N f_i(\alpha) = 1\) が成り立つ。（ただし、\(X_{N+1} = X_1\) と定める。）

\(\alpha\) を \(0\) から \(1\) に向かって連続的に増加させていくとき、\(f_i(\alpha) = \{\alpha(X_{i+1} - X_i)\}\) はほとんどの点のまわりで変化率 \(X_{i+1} - X_i\) で変化し、分母が \(|X_{i+1} - X_i|\) であるような有限個の有理数において、\(\pm 1\) 変化します。

\(\sum_i f_i(\alpha)\) は、ほとんどの点のまわりで定数で、有限個の点を境界として整数変化します。したがって、分母が \(|X_i - X_{i+1}|\) であるような有理数を列挙してソートするなどの計算によって、\(\alpha\) がどのような範囲にあるときに \(\{\alpha X_i\}\) が円周上に適切な位置関係で並ぶのかをすべて列挙することが可能です。\(\sum |X_i - X_{i+1}| = O(S)\) なので、これは \(O(S\log S)\) 時間で行えます。

さらに \(\alpha\) がこの条件を満たすとき、\(\beta\) が満たすべき条件は \(\{\alpha X_1 + \beta\} < \{\alpha X_N + \beta\}\) と表すことができます。結局、\(D\) の面積は、有限個の開区間 \((l,r)\) に対して \(\int_{l}^r \{\alpha (X_1 - X_N)\} d\alpha\) を加算することで計算することができます。

---

◆ \(\frac{g(K)}{K^2}\) が \(D\) の面積に収束することの証明

集合 \(D\subset \R^2\) の Lebesgue 測度を \(\mu(D)\) で表すことにします。また、\(D\) の内部・閉包をそれぞれ \(D^{\circ}\), \(\overline{D}\) と書くことにします。また、集合 \(D\) の定義関数 \(\chi_D\) を、\(\chi_D(x) = \begin{cases} 1 & (x\in D)\\0 & (x\notin D)\end{cases}\) により定めます。

次が成り立つことを示しましょう。

\(D\subset \mathbb{R}^2\) が有界で、その境界が零集合であるとする。つまり\(\mu(D^{\circ}) = \mu(\overline{D})\) が成り立つとする。\(a, b\in \mathbb{Z}\) であって \((a/K, b/K) \in D\) となるものの個数を \(g(K)\) と書くとき、\(\lim_{K\to\infty} \frac{g(K)}{K^2} = \mu(D)\) が成り立つ。

次のように点集合 \(A_K, A_K^{\circ}, \overline{A}_K\) を定めます。

• \(A_K = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, (a,b) \in D\}\)
• \(A_K^{\circ} = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, [a,a+1/K) \times [b,b+1/K) \subset D^{\circ}\}\)
• \(\overline{A}_K = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, [a,a+1/K) \times [b,b+1/K) \cap \overline{D}\neq \emptyset\}\)

また、関数 \(F^{\circ}_K, \overline{F}_K\) を

• \(F^{\circ}_K\) は、\(\bigcup_{(a,b)\in A_K^{\circ}} [a,a+1/K)\times [b,b+1/K)\) の定義関数
• \(\overline{F}_K\) は、\(\bigcup_{(a,b)\in \overline{A}_K} [a,a+1/K)\times [b,b+1/K)\) の定義関数

として定めます。このとき、次が確認できます。

• \(A_K^{\circ}\subset A_K\subset \overline{A}_K\)
• \(\int_x F^{\circ}_K(x) dx = |A_K^{\circ}| / K^2\)
• \(\int_x \overline{F}_K(x) dx = |\overline{A}_K| / K^2\)
• \(\lim_{K\to\infty} F^{\circ}_K(x) = \chi_{D^{\circ}}(x)\) （各点収束）
• \(\lim_{K\to\infty} \overline{F}_K(x) = \chi_{\overline{D}}(x)\) （各点収束）

\(D\) の有界性より Lebesgue の収束定理が適用できて、\(\lim_{K\to\infty} \int_{\R^2}F^{\circ}_K(x)dx = \int_{\R^2}\chi_{D^{\circ}}(x)dx\) が分かります。したがって、\(\lim_{K\to\infty} |A^{\circ}_K|/K^2 = \mu(D^{\circ})\) が成り立ちます。同様に、\(\lim_{K\to\infty} |\overline{A}_K|/K^2 = \mu(\overline{D})\) が成り立ちます。

\(A_K^{\circ}\subset A_K\subset \overline{A}_K\)、\(\mu(D^{\circ}) = \mu(\overline{D})\) およびはさみうちの原理から、\(\lim_{K\to\infty} |A_K|/K^2 = \mu(D)\) が成り立つことが分かります。これが示すべきことでした。

---

本問題における \(D\) は、有限個の \(1\) 次不等式で定義される領域の和集合であり、その境界は有限個の直線の和集合に含まれます。したがって、境界が零集合であるという上述の仮定を満たしています。