\([1]\) \(M\) が偶数の時

\(k\) を \(M=2k\) を満たす整数として、 \(S_1 = \left( N,2N, \cdots , kN, kN+1 , \left( k+1 \right)N +1 , \cdots , \left( M-1 \right) N +1 \right)\) とします。

\(S_{i+1}\) は \(S_i\) の前 \(k\) 個から \(1\) 引いたもの、後ろ \(k\) 個に \(1\) 足したものとすれば条件を満たします。

例えば、 \(\left( N,M \right)=\left(5,4 \right)\) なら \(S_1 = \left(5,10,11,16 \right), S_2 = \left( 4,9,12,17 \right) , S_3 = \left(3,8,13,18 \right) , \cdots\) となります。

\([2]\) \(M\) が奇数の時

\([\rm{I}]\) \(N\) が偶数の時

\(l\) を \(N=2l\) を満たす整数とします。 \(1\) から \(NM\) までの総和は \(\left(2Ml+1\right)Ml\) であり、 \(2Ml+1,M\) は共に奇数なので \(\left(2Ml+1\right)Ml\) は \(N=2l\) の倍数ではありません。

よってこの場合は不可能です。

\([\rm{I\hspace{-.01em}I}]\) \(N\) が奇数の時

\(M=1\) の時、 \(N=1\) なら \(S_1 = \left( 1 \right)\) とすることで可能です。 \(N \geq 3\) においては \(S_i\) が \(1\) つの数しか含まないので総和の条件に反してしまいます。

\(M \geq 3\) とします。ここで、 \(M = x\) の時に 平等な書き込み方 が存在するとします。 \([1]\) より \(M = 2\) の時に 平等な書き込み方 が存在するので、後者の \(S_{i,j}\) に \(Nx\) を足したものを前者に付け加えれば \(M = x+2\) でも 平等な書き込み方 が構成できます。

これを帰納法的に考えることで \(n\) を正整数として \(M = x\) の時に存在するならば \(M = x + 2n\) の時も存在することが示せます。

\(M = 3\) として 平等な書き込み方 が存在するかを考えます。 \(3\) で割った余りが \(0,1,2\) のものを \(1\) つずつ選んで \(S_i\) を構築するとして、選んだ数を \(3\) で割った商を考えると問題は以下のように帰着できます。

数列 $P,Q,R = \left( 0,1,2, \cdots N-1 \right)$ がある。 $P,Q,R$ を自由に並び替えて $P_i+Q_i+R_i$ を $i$ に依らず等しくすることができるか判定せよ。

\(R\) は \(\left( N-1,N-2, \cdots ,0 \right)\) としても問題ありません。よって \(P,Q\) を並び替えて 0-indexed とした時に \(P_i + Q_i = \frac{N-1}{2}+i\) とできるかを求めればよいです。

これは \(P = \left( 0,1,2, \cdots N-1 \right) , Q = \left( \frac{N-1}{2} , \frac{N-1}{2}+1 , \cdots , N-1 , 0 , 1 , \cdots , \frac{N-1}{2}-1 \right)\) とした後 \(P_i+Q_i\) に基づいて \(\{ P_i,Q_i \}\) をソートすればよいです。

以上より \(M = 3\) で構築できることが示されたので、 \(\left(N, M \right)=\left(1,1\right)\) もしくは \(M \geq 3\) では構築可能です。