tester 解で

\(y_{\text{min}}(a) < y_{\text{max}}(a)\) を満たす区間は各区間で \(y_{\text{min}}(a)\) と \(y_{\text{max}}(a)\) が両方線分となるような高々 \(4\) 個の区間に分割できます。

という記述がありますが，本解説ではこの事実を証明します．

準備として，長さ \(N\) の数列 \(X = X_0, \dots, X_{N-1}\) と実数 \(a\) について，\(I_{\max}(a; X), I_{\min}(a; X)\) を以下のように定義します．

\[ I_{\max} (a; X) \coloneqq \underset{k = 0, \dots, N-1}{\mathrm{argmax}} \{X_k - ak\} \]

\[ I_{\min} (a; X) \coloneqq \underset{k = 0, \dots, N-1}{\mathrm{argmin}} \{X_k +1 - ak\} \]

\(I_{\max}\) についての性質

以下の補題Aを証明します．

長さ \(N (\geq 3)\) の整数列 \(X\) が以下の性質を満たすとする．
1. \(X_0 \leq X_1 \leq \dots \leq X_{N-2}\)
2. \(\max\{X_{N-2}, X_{N-1}\} > X_0\)
3. ある実数 \(a, b\) が存在し，以下の条件 (P) が成り立つ．
(P) : \(i = 0, \dots, N-2\) について \(X_i = \lfloor ai + b \rfloor\) が成りたち，かつ \(X_{N-1} \leq \lfloor a(N-1) + b \rfloor\) ．

このとき，(P) が成り立つ \(b\) が存在するような実数 \(a\) の集合を \(A(X)\) とおくと，サイズ \(2\) 以下の集合 \(B\) が存在し，任意の \(a \in A(X)\) について \(I_{\max} (a; X) \cap B \neq \empty\) が成り立つ．

補題Aの証明

\(N\) についての数学的帰納法により示す．

数列から整数の定数を引いて，\(X_0 = 0\) を前提とする．
\(N = 3\) の場合，\(X_2\) と \(2X_1\) の大小関係で場合分けする． \(X_2 \geq 2X_1\) の場合，\(B = \{0, 2\}\) が補題の条件を満たす．
\(X_2 <2 X_1\) の場合，これは \(X_2 \leq 2X_1 - 1\) と同値である．\(2 \in I_{\max} (a; X)\) なる \(a \in A(X)\) が存在すると仮定すると，\(X_2 - 2a \geq X_1 - a\) より \(a \leq X_2 - X_1 \leq X_1 - 1\) である．一方で，\(a \in A(X)\) より，条件(P)を満たす実数 \(b\) が存在するため，\(a + b \geq X_1, b < 1\) より \(a > X_1 - 1\) となり，矛盾．よって，\(B = \{0, 1\}\) とすれば補題の条件を満たす．
以上から，\(N = 3\) の場合に補題が示された．

\(n > 3\) として，\(N = 3, \dots, n-1\) について補題が成り立つことを仮定する．\(N = n\) の場合に補題が成り立つことを示す．
数列の条件から，\(\Delta X \coloneqq \min_{k = 0,\dots, N-3}\{X_{k+1} - X_k\}\) として，\(Y_k \coloneqq X_k - \Delta Xk\) とすると，\(k \leq N-3\) について \(Y_{k+1} - Y_{k} \in \{0, 1\}\) かつ \(Y_{N-1} \leq Y_{N-2} + 1\) であり，特に \(Y_{k+1} = Y_k\) なる \(k\) が存在する．
また，\(I_{\max} (a; Y) = I_{\max}(a + \Delta X; X)\) であり，\(A(Y) = A(X) - \Delta X\) であるから，\(Y\) について補題の条件を満たす \(B\) が存在すれば，\(B\) が \(X\) について補題の条件を満たす．

\(Y_{N-2} = 0\) の場合，\(Y_{N-1} \geq 0\) の場合は \(B = \{0, N-1\}\) が補題の条件を満たすことが，\((k, Y_k)\) の上側凸包を考えることでわかる．一方で，\(Y_{N-2} < 0\) の場合は \(B = \{0, N-2\}\) が条件を満たすことがわかる（\(N-1 \in I_{\max}(a; Y)\) を満たすような \(a\) は \(a \in A(Y)\) を満たさない）．

\(Y_{N-2} > 0\) の場合を考える．この場合，\(a < 0\) で条件 (P) を満たす \(b\) が存在しないため，\(A(Y) \subset \mathbb{R}_{>0}\) となる．\(Y_k \leq Y_{k-1}\) の場合，\(a > 0\) について \(Y_k - ak \leq Y_{k-1} - a(k-1) + a < Y_{k-1} - a(k-1)\) であるから，\(k \notin I_{\max} (a; Y)\) である
ゆえに，\(N' \coloneqq \max\{Y_{N-2}, Y_{N-1}\} + 1\) とおいて，\(k = 0, \dots, N' - 1\) について \(Z_k \coloneqq \min \{i \mid Y_i = k\}\) とおくと，\(I_{\max} (a; Y) \subset \{Z_0, \dots, Z_{N' - 1}\}\) が成り立つ．\(N' \leq 2\) の場合，これで補題が示された．

以下，\(N' \geq 3\) の場合に限定する．
数列 \(Z\) を順番を逆にして \(-1\) 倍した数列 \(Z' = -Z_{N'-1}, \dots, -Z_0\) を考える．\(Y\) について条件 (P) を満たす \((a, b)\) について \(Z_k\) の定義より，\(k = 1, \dots, N'-1\) について

\[ a (Z_k - 1) + b < k \leq a Z_k + b \]

が成り立ち，変形することで

\[ - Z_{N'-1-k} \leq \frac{k}{a} + \frac{b - N'+1}{a} < -Z_{N'-1-k} + 1 \]

がわかる．同様の変形により，\(-Z_0 \leq \frac{N'-1}{a} + \frac{b-N'+1}{a}\) もわかり，\((\frac{1}{a}, \frac{b-N'+1}{a})\) が \(Z'\) について条件 (P) を満たすことがわかる．加えて，\(Z'\) は単調増加列であるから，\(Z'\) は補題の数列 \(X\) の要請を満たす．
さらに，\(Y\) の性質から \(N' < N\) であるため，仮定より \(Z'\) について補題を適用でき，補題の条件を満たす \(B'\) が存在することがわかる．
\(a \in A(Y)\) なる任意の \(a\) について，上記の変形により \(\frac{1}{a} \in A(Z')\) が導けるため，\(f(x) = \frac{1}{x}\) について \(f(A(Y)) \subset A(Z)\) がわかる．さらに，単射 \(z(k) = Z_k\) を考えると，

\[\begin{aligned} I_{\max} (a; Y) &= \arg\max_{k} \{Y_k - ak\}\\ &= z(\arg\max_{k} \{k - aZ_k\})\\ &= z(\arg\max_{k} \{\frac{k}{a} - Z_k\})\\ &= z(N'-1- \arg\max_k \{\frac{N'-1-k}{a} +(-Z_{N'-1-k})\})\\ &= z(N' - 1 - \arg\max_k \{Z'_k - \frac{k}{a}\})\\ &= z(N'-1-I_{\max} (\frac{1}{a}; Z')) = z(N'-1-I_{\max} (f(a); Z')) \end{aligned}\]

であるから，\(B = z(N' - 1 - B)\) が \(Y\) について補題の条件を満たすため，\(N = n\) の場合に補題が示された．

以上から，補題が示された．

\(I_{\min}\) についての性質

以下の補題Bを証明します．

長さ \(N (\geq 3)\) の整数列 \(X\) が以下の性質を満たすとする．
1. \(X_1 \leq \dots \leq X_{N-1}\)
2. \(\min\{X_0, X_1\} < X_{N-1}\)
3. ある実数 \(a, b\) が存在し，以下の条件 (Q) が成り立つ．
(Q) : \(i = 0, \dots, N-2\) について \(X_i = \lfloor ai + b \rfloor\) が成りたち，かつ \(X_{0} \geq \lfloor b \rfloor\) ．

このとき，(Q) が成り立つ \(b\) が存在するような実数 \(a\) の集合を \(C(X)\) とおくと，サイズ \(3\) 以下の集合 \(D\) が存在し，任意の \(a \in C(X)\) について \(I_{\min} (a; X) \cap D \neq \empty\) が成り立つ．

補題 A とは違い，集合 \(D\) のサイズの上限は \(3\) であることに注意してください．
証明は補題 A と同様にして行えます．

補題 B の証明

\(N\) についての数学的帰納法により示す．

\(N = 3\) の場合は自明．

\(N = 3, \dots, n-1\) の場合に補題を仮定して，\(N = n\) の場合を示す．
適切に定数を引いて \(\min X = 0\) となるようにし，\(I_{\max}\) の場合と同様に \(Y\) を作成し，適切の定数を引いて \(\min Y = 0\) となるようにする．補題 A と同様の議論を行うことで，数列 \(Y\) に対して補題 B の条件を満たすような \(D\) が存在すれば十分であることがわかる．
\(Y_1 = \dots = Y_{N-1}\) の場合，\(Y_0 \leq Y_1\) ならば \(D = \{0, N-1\}\) が，\(Y_0 > Y_1\) ならば \(D = \{0, 1, N-1\}\) が補題 B の条件を満たす．
\(Y_1 < Y_{N-1}\) の場合，\(C(Y) \subset \mathbb{R}_{>0}\) である．よって，\(Y_k \geq Y_{k+1}\) を満たす \(k\) について，任意の \(a \in C(Y)\) について \(Y_k + 1 - ak \geq Y_{k+1} + 1 - ak > Y_{k+1} + 1 - a(k+1)\) である．\(N' \leq 3\) の場合は自明であるため，\(N' \geq 4\) の場合に限定する．
ゆえに，\(Z_k \coloneqq \max_i \{Y_i = k\}\) とおくと，\(I_{\min} \subset \{Z_0, \dots, Z_{Y_{N-1}}\}\) がわかる．
\(N' = Y_{N-1} + 1\) として，数列 \(Z' = -Z_{N'-1}, \dots, -Z_{0}\) を考える．補題 A の証明と同様の計算により，\(Y\) について条件 (Q) を満たす任意の \((a, b)\) について，\((\frac{1}{a}, \frac{a+b-N'}{a})\) が \(Z'\) について条件 (Q) を満たすことがわかり，明らかに単調増加列であるため補題 B の要請を満たす．
よって，\(N' < N\) と仮定を合わせることで，\(Z'\) について補題 B の条件を満たす集合 \(D'\) が存在することがわかる．

最後に，補題 A の証明と同様の変換を行うことで，\(D = z(N'-1-D')\) が \(Y\) について補題 B の条件を満たすことがわかるため，補題 B は示された．

Tester 解の事実の証明

補題 A, B より，\(I_{\max}\) は高々 \(2\) 個の，\(I_{\min}\) は高々 \(3\) 個のインデックスが支配的であり，\(a\) の増加に伴って \(I_{\max}\) は減少し，\(I_{\min}\) は増加する．よって，インデックスの切り替わりは高々 \((2-1) + (3-1) = 3\) 回発生し，区間は高々 \(4\) つに分割される．

補題 A, B の要請を満たさない場合について考える．
補題の 3 番目の要請は必ず満たされるため，1, 2 番目の要請が満たされない場合に限定する．
1 番目の要請が満たされて 2 番目の要請が満たされない場合，\(X_0 = \dots = X_{N-1}\) であり，この場合は \(I_{\max}, I_{\min}\) は \(0\) か \(N-1\) になり，区間は高々 \(4\) つに分割される．
1 番目の要請が満たされない場合は，\(X\) は単調非増加列である．この場合は，\(X' = -X_{N-1}, \dots, -X_0\) を考えると補題の要請を満たすことがわかる．\(I_{\max} (a; X) = N-1-I_{\max}(-a; X'), I_{\min} (a; X) = N-1-I_{\min}(-a; X')\) であるから，区間は高々 \(4\) つに分割される．