各 \(1 \leq i \leq N\) に対して \(d_i = \lvert A_{i-1}-A_i \rvert \) とします。 \(i-1\) 項目の大小と \(i\) 項目の大小は \(A, B_1, \ldots, B_k\) において一致しているので、 \(d_i = \sum_{j=1}^k \lvert B_{j,i-1} - B_{j,i} \rvert \) となります。右辺の各項は \(1\) 以上であるので \(k \leq d_i\) が必要です。 つまり、\(k \leq \min_{1 \leq i \leq N} d_i\) が必要です。

実は \(k = \min_{1 \leq i \leq N} d_i\) の場合に \(B_1, \ldots, B_k\) を構成することができます。 各 \(0 \leq i \leq N\) について、\(A_i\) をできるだけ均等に \(k\) 分割します。 具体的には \(B_{j,i} = \left\lfloor\frac{A_i+j-1}{k} \right\rfloor\) とします。 \(k \leq d_i\) であることを用いると、各 \(B_j\) が良い非負整数列となることが確認できます。