\(p_i<p_j<p_k\) を満たすとき、\((i,j,k)\) を上昇三つ組とします。同様に、\(p_i>p_j>p_k\) を満たすとき、\((i,j,k)\) を下降三つ組とします。順列 \(P\) について、それぞれの個数を順に \(U,D\) とします。目標は、\(U=D\) とすることです。

まず、結論として、条件を満たす順列 \(P\) は必ず存在します。

基本的な方針は、\(P_k\) と \(P_{N-k}\) にそれぞれ \(2k-1,2k\) のいずれかを割り当てる、というものです。この時、\(U-D\) について考えます。

\((i,j,k)\) が上昇三つ組だったとします。すると、\((N-k,N-j,N-i)\) は、多くの場合で下降三つ組になります。具体的には、\(i+j,j+k,k+i≠N\) を満たす場合、それは必ず下降三つ組になります。逆も同様です。よって、考えるべきなのは、\((i,j,N-j)\) の場合と、\((i,N-i,j)\) の場合のみになります。(\((i,j,N-i)\) の場合については、明らかにこれは上昇三つ組でも下降三つ組でもないので考える必要はありません。)

\(P_k\) に割り当てる数字を決めることにします。すると、それぞれの場合において、先ほどの考察より \(U-D\) の値の変化は以下のようになります。

• \(P_k\) に \(2k-1\) を割り当てた場合、\(U-D\) の値は \(k-1\) だけ増加する。
• \(P_k\) に \(2k\) を割り当てた場合、\(U-D\) の値は \(k-1\) だけ減少する。

結局のところ、以下の問題が \(n=M\) の場合で解ければ、この問題の \(N=2M\) の場合に正解することができます。

• 集合 \(S=\{0,1,\dots,n-1\}\) がある。\(S\) を、総和が等しくなるように集合 \(T_1\) と \(T_2\) に分割せよ。

しかし、この問題の答えは、任意の \(n\) に対して存在するとは限りません。まず、\(\dfrac{n(n-1)}{2}\) が偶数でない場合は、明らかに不可能です。逆に、それが偶数になる場合、つまり \(n \equiv 0,1\pmod 4\) の場合は、構築が可能です。具体的には、以下のようにして構築することができます。( \(T_2\) については省略します)

• \(n \equiv 0\pmod 4\) のとき、\(T_1=\{0,3,4,,\dots,n-4,n-1\}\)
• \(n \equiv 1\pmod 4\) のとき、\(T_1=\{0,1,4,5,8,\dots,n-4,n-1\}\)

ここまでの考察で、\(N \equiv 0,2\pmod 8\) の場合は解くことが出来ました。では、それ以外の場合はどうでしょうか？ 実は、すべての \(N\) に対して、列 \(Q\) であって、\(N \equiv 0,2\pmod 8\) の場合の構築の前半 \(\dfrac{N}{2}\) 項と、後半 \(\dfrac{N}{2}\) 項との間に \(Q\) を挿入することでその列が条件をみたすようなものが存在します。具体的には、以下のようにすれば良いです。

• \(N \equiv 1,3\pmod 8\) の場合、\(Q=(N)\) とすれば良い。
• \(N \equiv 4,6\pmod 8\) の場合、\(Q=(N-2,N,N-3,N-1)\) とすれば良い。
• \(N \equiv 5,7\pmod 8\) の場合、\(Q=(N-3,N,N-2,N-4,N-1)\) とすれば良い。

証明は、\(Q\) について、上昇三つ組の個数と下降三つ組の個数が等しいこと、また \(Q\) の転倒数が \(\frac{|Q|(|Q|-1)}{4}\) と等しいことを考慮し、寄与を具体的に考えることで示すことができます。

よって、任意の \(N\) に対して、条件を満たす \(P\) を \(O(N)\) で構築することができました。