ジャグリングの数理

$h_f(t + kp) = h_f(t)$より従う。

補題1より、$t \equiv s \pmod p$ならば$f(t) \equiv f(s) \pmod p$である。これはすなわち$t \equiv s \pmod p$ならば$f'(s) \equiv f'(t) \pmod p$であることを示しているから$f'$はwell-definedである。次に全単射性を示すが、全射性のみ示せば十分。$t \in \mathbb{Z}/p\mathbb{Z}$とする。$f$は全単射であるから、$f(s) = t$を満たす$s \in \mathbb{Z}$がある。ここで補題1より、$s' = s \pmod p$とすれば、$s' \in \mathbb{Z}/p\mathbb{Z}$であって$f(s') \equiv t \pmod p$である。よって$f'$は全射であることが示せた。

($\Rightarrow$)数列$\{a_i\}_{i = 0}^{p-1}$がJugglableであるとする。すなわち、あるジャグリングパターン$f$があって、$h_f(i) = a_i$である。補題2より任意の$i \in \mathbb{Z}/p\mathbb{Z}$に対し$f(i) \equiv \pi_{f}(i) \pmod p$となる置換$\pi_{f}$が存在するが、
$$a_i = h_f(i) = f(i) - i \equiv \pi_{~f}(i) - i \pmod p$$
より、$a_i + i \equiv \pi_{f}(i) \pmod p$が得られる。置換は全単射であるから、$\phi_{\{a_i\}}$も全単射である。

($\Leftarrow$)$\phi_{\{a_i\}}$が置換であったとする。$\{a_i\}_{i = 0}^{p-1}$がJugglableであることを示すには任意の$i \in \mathbb{Z}/p\mathbb{Z}$に対し$h_f(i) = a_i$となるようなジャグリングパターン$f$を見つければ良い。数列$\{a_i\}_{i=0}^{p-1}$を拡張し、$j \in \mathbb{Z}$に対し$a_j = a_i \left(j \equiv i \pmod p\right)$と定義する。ここで、$$f \colon \mathbb{Z} \to \mathbb{Z} ; j \longmapsto a_j + j$$
という関数を考え、これがジャグリングパターンとなっていることを示す。$h_f(j) = a_j$は$f$の作り方から満たされていることがすぐ分かるから、任意の$k,j \in \mathbb{Z}$に対し$h_f(j + kp) = h_j(j)$、任意の$i \in \mathbb{Z}/p\mathbb{Z}$対し$f(i) \geq i $と$f$が全単射になっていることを確かめれば良い。$ \displaystyle{ \begin{align} h_f(j + kp) &= f(j + kp) - (j + kp) \\ &= a_{j + kp} \\ &= a_j + j - j\\ &= f(j) - j\\ &= h_f(j) \end{align} }$
より$h_f(j + kp) = h_j(j)$は成立。また、$f(i) \geq i $は$a_i$が非負であることから明らか。
あとは$f$が全単射であることを示す。

(単射性)$s, t \in \mathbb{Z}$に対し$f(s) = f(t)$であったとする。このとき、$f$の定め方から$\phi_{\{a_i\}}(s) = \phi_{\{a_i\}}(t)$である。$\phi_{\{a_i\}}$は全単射であると仮定しているから、$s \equiv t \pmod p$が成り立つ。すなわち、$a_s = a_t$である。これと$f(s) = f(t)$より$s = t$が言えるから、単射性は示された。

(全射性)$\phi_{\{a_i\}}$は全単射であるから、ある$s' \in \mathbb{Z}/p\mathbb{Z}$に対し、$\phi_{\{a_i\}}(s') \equiv t \pmod p$となる$t \in \mathbb{Z}$がある。すなわち、$a_{s'} + s' \equiv t \pmod p$が成り立っている。ここで、$a_{s'} + s' + kp = t$とすると、$a_{s'} = a_{s' + kp}$であるから
$ \displaystyle{ \begin{align} f(s' + kp) &= a_{s' + kp} + s' + kp\\ &= a_{s'} + s' + kp\\ &= t \end{align} }$
よって、$s =s' + kp$とおけば、任意の$s \in \mathbb{Z}$に対して$f(s) = t$となる$t \in \mathbb{Z}$がとれるため、$f$は全射である。

$s$がJugglableであると仮定する。$s_{m,n}$の定義より、
$ \displaystyle{ \begin{align} \begin{cases} a'_n + n = a_m + m\\ a'_m + m = a_n + n\\ a'_i + i = a_i + i \quad (i \not = m, n) \end{cases} \end{align} }$
が成り立つ。すなわち、写像
$$\phi_{\{a'_i\}} \colon \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z} ; i \longmapsto a'_i + i \pmod p$$
は、写像$$\phi_{\{a_i\}} \colon \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z} ; i \longmapsto a_i + i \pmod p$$と互換$(m,n)$の合成で書ける。$\phi_{\{a_i\}}$と互換$(m,n)$は全単射であるから、$\phi_{\{a'_i\}}$も全単射。よって$s_{m,n}$はJugglableである。逆に関しても同様の議論で示すことができる。

$a'_m + a'_n = a_n + (n-m) + a_m - (n-m) = a_n + a_m$より示せる。

$s$がJugglableであると仮定する。$s_{\rightarrow}$の定義より、
$$\phi \colon \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z} ; i \longmapsto a_i + i + 1 \pmod p$$
が全単射であることを示せば、$s_{\rightarrow}$がJugglableであることが示せるが、$s$のJugglable性よりこれは明らかに全単射。

サイクリックシフトは数列の順番を入れ替えているだけであるから、数列の平均は保たれる。

$\{a_i\}_{i =0}^{p-1}$はJugglableであるから、
$$\sum_{i = 0}^{p-1}(a_i + i) \equiv \sum_{i = 0}^{p-1} i \pmod p$$
よって、
$$\sum_{i = 0}^{p-1}(a_i + i) \equiv 0 \pmod p$$
$\{a_i\}_{i =0}^{p-1}$は非負数列であるから、$\frac{1}{p}\sum_{i = 0}^{p-1}a_i$は非負整数である。

siteswapとサイクリックシフトは逆元を持つ操作であるから、与えられたJugglableな数列$s = \{a_i\}_{i =0}^{p-1}$にsiteswapとサイクリックシフトを施して$\overbrace{bb\ldots b}^{p個}$へと変換できることを示せば良い。そこで、以下のアルゴリズムを考える。

1. $s$が定数列であれば操作を終える。そうでないならば2.へ進む。
2. $i$を$a_i$が$s$の中で最大かつ$a_{i+1} < a_i$となるように選ぶ。$s$にi-シフトを施し、先頭に$a_i$が、その次に$a_{i+1}$が来るようにし、3.へ進む。
3. $s \to s_{1,2}$とsiteswapを施し、1.へ戻る。

手順2.で$a_i - a_{i+ 1} = 1$の場合は手順3.でsiteswapを施しても最大値と最大値をとる$a_i$の個数は変わらない。しかし、$s$はJugglableであるから、定理3より$a_i - a_{i+ 1} =1$とはなり得ない。よって、手順3.によって数列$s$の最大値は必ず1だけ減るか、または最大値をとる$a_i$の個数が1だけ減る。よってこのアルゴリズムは有限回で終了し、それは$s$が定数列へと変換された時である。さらに定理5と7より数列の平均は保たれるから、このアルゴリズムで数列は$\overbrace{bb\ldots b}^{p個}$へ変換されることが分かる。

$\overbrace{bb\ldots b}^{p個}$をジャグリングするにはb個のボールが必要なのは明らか(b拍後に手に戻ってくる高さでボールを投げ続けるため、b個のボールが必要)。この事実と定理4、6、9より、数列の平均$b$は必要なボールの数と一致することが分かる。