アーベル群の置換とジャグリング

はじめに(非ジャグラー向け)

位数$n$の有限アーベル群$A$を考える. ここで,
\begin{eqnarray} \left( \begin{array}{cccc} a_1 & a_2 & \cdots &a_n\\ c_1 & c_2 & \cdots &c_n \end{array} \right) \end{eqnarray}
のような$A$の置換を考える. このとき, 差分列$\{b_i\}_{i=1}^n := \{c_i - a_i\}_{i=1}^n$は必ずしも$A$の順列になっているわけではないが, $\sum_i^n b_i = 0$を満たしている.
この逆を考える. つまり,

残念ながらこれは真ではない. そこで, 数列$\{b_i\}_{i=1}^n$の並べ替えを許容することにする.
つまり,

という問題を考える.

はじめに(ジャグラー向け)

ある数列$\{a_i\}_{i=1}^n$がJugglableであることの必要条件に, 数列の平均$ \sum_{i=1}^{n}a_i / n $が整数値であること, というものがありました.
当然ですが, 逆は偽です.実際$135$や$8484641$などの数列は, 平均が整数ですがJugglableではありません.

しかしながらこれらの数列は, 適切に並び替えることによってJugglableになります.

例えば, $135 \to 531$や, $8484641 \to 8448641$と並び替えることによって, Jugglableにすることができます.

ここで疑問に思うのは, 「平均が整数になる列は, 適切に並び替えれば必ずJugglableにできるか？」ということです.

並べ替え定理

上述の問題は, 一般的な性質であることが証明されています.

サイトスワップの問題に焼き直すには, $A$を$\mathbb{Z} / n\mathbb{Z}$に, 数列$\{b_i\}_{i=1}^n$をサイトスワップの数列に読み替えれば良いです.
以下は, Marshall Hallによる証明paperに沿います.

証明

$A$の相異なる元$a_1, a_2, \cdots, a_n$をある順番で固定する. 定理1の主張は, $\sum_{i=1}^{n} b_i = 0$を満たすような$A$の数列$\{b_i\}_{i=1}^n$を適切に並び替えて, 数列$\{c_i\}_{i=1}^n = \{a_i + b_i\}_{i=1}^n$が全て相異なるようにできるということに帰着する.

これを示すには, 以下の主張を示せば十分である.

実際, そのような操作が可能であれば, 恒等置換から始めて, 差分列が,
$(0, 0, \cdots, 0) \to (b_1, -b_1, 0, \cdots, 0) \to (b_1, b_2, -b_1 - b_2, 0, \cdots, 0)$のように変換できる. そうすると, 最終的に差分列は$(b_1, b_2, \cdots, b_{n-1}, -\sum_{i=1}^{n-1}b_i = b_n)$のようになり, 目的の置換を得ることができる.

ここで,以下の表のように, 最初の$n-2$個については, $a_i + b_i = c_i$となるように$\{b_i\}_{i=1}^{n-2}$を並び替えられている状況を考える.
\begin{eqnarray} \begin{array}{cccccccc} a_1 & a_2 & \cdots &a_{n-2} & a_{n-1} & a_n\\ b_1 & b_2 & \cdots &b_{n-2} & & & b_{n-1} & b_n\\ c_1 & c_2 & \cdots &c_{n-2} & & & u_{-1} & u_0 \end{array} \end{eqnarray}
この表においては, 数列$\{a_i\}_{i=1}^n$はある順番で固定されていて, $c_1, \cdots, c_{n-2}$は全て相異なるように$\{b_i\}_{i=1}^{n-2}$を配置できている. $b_{n-1}, b_n$は, 数列$\{b_i\}_{i=1}^n$の中で, まだ用いられていない余りである. また, $u_{-1}, u_0$は, $A$の元のうち, $\{c_i\}_{i=1}^{n-2}$に含まれないものである.

これはすなわち, 差分列$(b_1, b_2, \cdots,b_{n-2}, b'_{n-1}, b'_n)$から$b'_{n-1}, b'_n$を選んで, これらを$b_{n-1} + b_n = b'_{n-1} + b'_n$を満たすような$b_{n-1}, b_n$に入れ換える状況を考えている.

このとき,
\begin{eqnarray} \left(\sum_i^{n-2}a_i\right) + a_{n-1} + a_n + \left(\sum_i^{n-2}b_i\right) + b_{n-1} + b_n &=& \left(\sum_i^{n-2}c_i\right) + u_{-1} + u_0 \\ \therefore a_{n-1} + a_n + b_{n-1} + b_n &=& u_{-1} + u_0 \end{eqnarray}
のような保存則が成り立っている.

この式より, $a_{n-1}, a_n$と$b_{n-1}, b_n$から1つずつ選んで$u_{-1}$を作ることができるとすると, $u_0$は$a_{n-1}, a_n$と$b_{n-1}, b_n$のうち, $u_{-1}$を作る際に使っていないものを足し合わせて構成できる.
例えば, $a_{n-1} + b_n = u_{-1}$が成り立っている場合, $a_n + b_{n-1} = u_0$も同時に成立している.
この場合は, $b_{n-1}, b_n$を適切に並び替えることにより置換を得ることができる.

例えば, $a_{n-1} + b_n = u_{-1}$, $a_n + b_{n-1} = u_0$が成り立っている場合,
\begin{eqnarray} \begin{array}{cccccc} a_1 & a_2 & \cdots &a_{n-2} & a_{n-1} & a_n\\ b_1 & b_2 & \cdots &b_{n-2} & b_n& b_{n-1}\\ c_1 & c_2 & \cdots &c_{n-2} & u_{-1} & u_0 \end{array} \end{eqnarray}
のような置換を新たに得ることができ, 最後2列の差分ペアを、同じ和を保つ別のペアに置き換えるような操作を実際に行うことができる.

次に, $a_{n-1}, a_n$と$b_{n-1}, b_n$からどの組み合わせを選んでも$u_{-1}$を構成することができない場合を考える. このときには, 適切な置換を構成することができないため, すでに完成している列を使って, 数列$\{b_i\}_{i=1}^n$を並び替える必要がある.
そこで, 方程式
\begin{equation} x + b_{n-1} = u_{-1} \end{equation}
の解を$a_{r_1}$とする. 仮定より, $ 1 \leq r_1 \leq n-2$である. $b_{r_1}$を$b_{n-1}$に, $c_{r_1}$を$u_{-1}$に入れ換えれば,
\begin{eqnarray} \begin{array}{ccccccccc} a_1 & \cdots & a_{r_1} & \cdots &a_{n-2} & a_{n-1} & a_n & & \\ b_1 & \cdots & b_{n-1} & \cdots &b_{n-2} & & & b_{r_1} & b_n\\ c_1 & \cdots & u_{-1} & \cdots &c_{n-2} & & & u_0 & c_{r_1} \end{array} \end{eqnarray}
のような置換の表を得ることができる. また, 入れ換え前と同様の保存則として,
\begin{eqnarray} a_{n-1} + a_n + b_{r_1} + b_n &=& c_{r_1} + u_0 \end{eqnarray}
が成り立っている.
もし, $a_{n-1}, a_n$と$b_{n-1}, b_n$から$c_{r_1}$あるいは$u_0$を得ることができれば, それらを適当に並び替えることによって, 目的の置換を得ることができる.
そのような組み合わせがない場合は, 同様の手続きを行う.
すなわち, $x + b_{r_1} = u_0$となるような$x$を求め, それを$a_{r_2}$とし, 入れ換えを行う.

この一連の操作は, 目的の置換を得られずに無限に続くようなことはない.
もし, この入れ替えの操作が無限に続いたとする. $i$回目の入れ替え操作によって$a_{r_i}$が選ばれたとすると, この$r_i$は常に$\{1, \cdots, n-2\}$から選ばれるから, どこかで重複が生じる. よって, $a_1, a_2, \cdots, a_{r_i}, \cdots a_{r_j}$は全て異なり, $a_{r_i} = a_{r_j + 1}$が成り立つような$j \geq i$を選ぶことができる.
$j$回目の入れ換えでは, 次のような置換の表が得られている.
\begin{eqnarray} \begin{array}{ccccccccccc} a_1 & \cdots & a_{r_i} & \cdots &a_{r_j} & \cdots & a_{n-2} & a_{n-1} & a_n\\ b_1 & \cdots & b_{r_{i-1}} & \cdots &b_{r_{j-1}} & \cdots & b_{n-2} & & &b_{r_i} & b_n\\ c_1 & \cdots & c_{r_{i-2}} & \cdots &c_{r_{j-2}} & \cdots & c_{n-2}& & & c_{r_{i-1}} & c_{r_i} \end{array} \end{eqnarray}
ここで, $x + b_{r_j} = c_{r_{j-1}}$の解は$a_{r_{j+1}} = a_{r_i}$となっている. 入れ換えを行ったのちに余る数列$\{b_i\}_{i=1}^n$と$\{c_i\}_{i=1}^n$の元は, $b_{r_{i-1}}, b_n$と$c_{r_j}, c_{r_{i-2}}$であって, 保存則は,
\begin{eqnarray} a_{n-1} + a_n + b_{r_{i-1}} + b_n &=& c_{r_j} + c_{r_{i-2}} \end{eqnarray}
が得られる.
ところで, $i-1$番目の入れ換え後に得られる保存則は,
\begin{eqnarray} a_{n-1} + a_n + b_{r_{i-1}} + b_n &=& c_{r_{i-1}} + c_{r_{i-2}} \end{eqnarray}
である. 2つの保存則を比較すれば, $c_{r_j} = c_{r_{i-1}}$が得られるが, $j > i-1$であるから矛盾. 数列$\{c_i\}_{i=1}^n$は, $A$の順列になっているはずだから, 同じ元は含まれないはずである.
よって, この入れ換えの操作が無限に続くことはなく、高々$n-2$回の操作で目的の置換を得て停止する.

具体例

$A$として$\mathbb{Z}/5\mathbb{Z}$を考え, 数列$\{b_i\}_{i=1}^5$として, $0, 0, 1, 2, 2$を考える.
次に, 以下のような置換の表を考える.
\begin{eqnarray} \begin{array}{ccccccc} 0 & 1 & 2 & 3 & 4 & & \\ 0 & 0 & 1 & & & 2 & 2 \\ 0 & 1 & 3 & & & 2 & 4 \end{array} \end{eqnarray}
この表において, 左3列については条件を満たすような置換が完成している. しかし, 右2列は, どのような組み合わせをとってきても埋めることができない.
そこで, $x + 2 = 2$を解くと, $x = 0$となるから, 一番左の列について入れ換えを行う.
すると, このような置換の表を得る.
\begin{eqnarray} \begin{array}{ccccccc} 0 & 1 & 2 & 3 & 4 & & \\ 2 & 0 & 1 & & & 0 & 2 \\ 2 & 1 & 3 & & & 0 & 4 \end{array} \end{eqnarray}
これは, $3, 2$と$4, 0$を組にすることによって置換を完成させることができる.
すなわち, 数列$\{b_i\}_{i=1}^5$を$2, 0, 1, 2, 0$と並べ替えることによって,
\begin{eqnarray} \left( \begin{array}{ccccc} 0 & 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 0 & 4 \end{array} \right) \end{eqnarray}
のような目的の置換を得ることができる.

余談

2年ぐらい前に競プロ界隈で若干話題になったような覚えがあります. そのときには未解決問題なのではないかとされていました.