文献あり

ジャグリング可能なサイトスワップであるための必要十分条件

439

トスジャグリングの投げ方を表す方法にサイトスワップというものがあります。
この記事では次の定理を証明します。

（バニラ）サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ がジャグリング可能であるための必要十分条件は、 $i \neq j$ かつ $1 \leq i, j \leq n$ なる任意の $i, j$ に対し、
$\begin{array}{r} i + t_{i} ≢ j + t_{j} (\mod n) \end{array}$
が成立することである。

サイトスワップとは

サイトスワップはボール（またはその他の道具）を投げて行う周期的なジャグリングの技を説明するために用いられるものです。
サイトスワップがどういうものなのかを知るには参考文献に挙げた日本ジャグリング協会のHPのサイトスワップについてのページが分かりやすいと思います。知らない人はそちらを見てください。
ここにもリンクを貼っておきます。サイトスワップ‐日本ジャグリング協会

サイトスワップがどういうものか、一応ここでも紹介しておきます。
日本ジャグリング協会のHPではサイトスワップを次のように紹介しています。

サイトスワップ（siteswap）とは、ボールやクラブなどのトスジャグリングにおいて投げ上げる物体の高さを数列で表現したものです。

サイトスワップのより詳しい説明（ルール）として、日本ジャグリング協会のHPには次のように書かれています。

ボールは同じ時間間隔で、左右交互に投げる

数字は、今投げたボールを次に投げるまでの時間間隔を表す

この、ボール（またはその他の道具）を投げる各時間を拍といいます。
この記事では、これらの条件に「各拍に高々 $1$ 個のボールが投げられる」という条件を加えたものを考えます。このようなサイトスワップをバニラサイトスワップといいます。
例えば、 $1$ 拍目に $3$ という量で投げられたボールは、 $4$ 拍目に再び投げられます。
より一般に、 $n$ 拍目に $t_{n}$ という量で投げられたボールは、 $n + t_{n}$ 拍目に再び投げられます。
ただし、 $0$ のみ例外として該当の拍に投げられるボールがないことを表します。

このように、サイトスワップはボール等を投げる位置の情報を持ちません。
つまり、それぞれのボールを投げる拍の間隔さえ同じであれば、腕を交差させようが背面で投げようが同じサイトスワップとなります。

ジャグリングの状態と状態数

あるスローが行われた直後の状態をつぎのように定義します。

状態

状態は各項が $0$ か $1$ である数列であり、考えているスローが行われるのを $0$ 拍目として、そのスローが行われた直後の状態 $σ = {σ_{i}}_{i = 1}^{\infty}$ を次の式で定義する。
$\begin{aligned} σ_{i} & = {\begin{cases} 1 & (i 拍目に初めて投げられるボールがあるとき) \\ 0 & (それ以外) \end{cases} \\ (i = 1, 2, . . .) \end{aligned}$

状態の定義から、任意の状態 $σ$ に対してある $N \in N$ が存在して $σ_{N} = 1$ かつ $i > N$ ならば $σ_{i} = 0$ が成り立ちます。このとき、 $σ = (σ_{1}, σ_{2}, . . ., σ_{N})$ と書くことにします。

状態数

状態 $σ = {σ_{i}}_{i = 1}^{\infty}$ に対して、その状態数 $s (σ)$ は次の式で与えられる。
$\begin{array}{r} s (σ) = \sum_{i = 1}^{\infty} σ_{i} 2^{i - 1} \end{array}$

ここからは、各スローが状態にどのような変化をもたらすのかを見ていきます。
本題に入る前に、以降の話を円滑にするためにサイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ についてひとつ定義をしておきます。

サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ とは、第 $1$ 項から第 $n$ 項までが順に $t_{1}, t_{2}, . . ., t_{n}$ である周期 $n$ の非負整数列 ${t_{i}}_{i = - \infty}^{\infty}$ である。

では、スローによる状態の変化を見ていきましょう。
状態の定義より、次のようなことが成り立ちます。

状態の変化

ある状態 $σ = {σ_{i}}_{i = 1}^{\infty}$ を取ったとき、この状態からスロー $t_{1}$ を行った直後の状態 $σ^{'} = {σ_{i}^{'}}_{i = 1}^{\infty}$ は次の式で与えられる。
$\begin{aligned} σ_{i}^{'} & = {\begin{cases} 1 & (i = t_{1} のとき) \\ σ_{i + 1} & (それ以外のとき) \end{cases} \\ (i = 1, 2, 3, . . .) \end{aligned}$

どんな状態 $σ$ ならばスロー $t_{1}$ を行うことができるのでしょうか。
例えば、 $t_{1} = 0$ で $σ_{1} = 1$ のとき、 $σ_{1} = 1$ より $1$ 拍目にボールが落ちてくるはずですが、 $t_{1} = 0$ は $1$ 拍目に投げられるボールが存在しないことを示しています。そのため、このような状況では状態 $σ$ から、スロー $t_{1}$ を行うことはできません。
では $t_{1} > 0$ の時はどうでしょうか。今、我々はバニラサイトスワップを考えているので、ひとつの拍で高々 $1$ つのボールしか投げられません。したがって、 $σ_{1 + t_{1}} \neq 1$ である必要があります。
これらのことを一般化すると、サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ がジャグリング可能であるための必要条件としてつぎが得られます。

ジャグリング可能であるための必要条件

サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ がジャグリング可能であるためには
$i \neq j$ かつ $1 \leq i, j \leq n$ なる任意の $i, j$ に対し、
$\begin{array}{r} i + t_{i} ≢ j + t_{j} (\mod n) \end{array}$
であることが必要。

この条件は、 $1$ 拍で $2$ つ以上のボールを投げないという条件を表したものです。
そこで、サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ はジャグリング可能だが、 $1 \leq i < j \leq n$ なるある $i, j$ が存在して、 $i + t_{i} \equiv j + t_{j} (\mod n)$ であると仮定します。
$t_{1}$ を投げる拍を $1$ 拍目として、 $1$ 拍目よりも充分前の拍からジャグリングしているという仮定もします。（このような仮定は $T$ がジャグリング可能であることから可能。）
すると、ある $d \in Z$ が存在して、 $i + t_{i} = j + t_{j} + d n = j + d n + t_{j + d n}$ です。
これは、 $i$ 拍目と $j + d n$ 拍目に投げたボールが、 $i + t_{i}$ 拍目まで $1$ 度も投げられることなく、どちらも $i + t_{i}$ 拍目に投げられることを意味しています。
これは、 $1$ 拍のうちに $2$ つ以上のボールを投げないというバニラサイトスワップの条件に反しているので、背理法により、定理の内容が従います。 $◻$

つづいて、スロー $t_{i} (i \in N)$ によって状態数がどのように変化するかを見ていきましょう。スロー $t_{i}$ を投げる直前の状態を $σ^{(i - 1)}$ ,投げた直後の状態を $σ^{(i)}$ とします。すると、状態数の定義とスローによる状態の変化の仕方から、以下の式が成立することがわかります。
$\begin{array}{r} s (σ^{(i)}) = \frac{1}{2} (s (σ^{(i - 1)}) - 1 + 2^{t_{i}}) \end{array}$

ジャグリング可能なサイトスワップであるための必要十分条件

ジャグリング可能の定義

前節でサイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ がジャグリング可能であるための必要条件が得られました。そこで、この条件（以下この条件を「条件＊」と呼ぶ）を満たすサイトスワップ $T$ に対し、ジャグリング可能であることを次のように定義します。

サイトスワップ $T$ がジャグリング可能であるとは、 $T$ が条件＊をみたし、ある初項 $s_{0}$ が存在して、以下の漸化式で定まる数列 $S (T, s_{0}) = {s_{i}}_{i = 0}^{\infty}$ が非負整数列となることである。
$\begin{aligned} s_{i} & = \frac{1}{2} (s_{i - 1} - 1 + 2^{t_{i}}) & (i = 1, 2, 3, . . .) \end{aligned}$

この定義にはジャグリングのパターンが周期的であることが含まれていませんが、ジャグリング可能なサイトスワップ $T$ によって定まるパターンが周期的であることは以下の定理からわかります。

$T$ がジャグリング可能なサイトスワップで $S (T, s_{0})$ が非負整数列なら、 $S (T, s_{0})$ は周期数列となる。

まず、 $S (T, s_{0})$ が有界であることを示す。
$\begin{array}{r} M = max {s_{0}, max_{1 \leq i \leq n} {2^{t_{i}} - 1}} \end{array}$
とする。
任意の非負整数 $i$ に対し、 $0 \leq s_{i} \leq M$ であることを示す。
$S (T, s_{0})$ が非負整数列であることから $s_{i} \geq 0$ は明らか。
任意の非負整数 $i$ に対し、 $s_{i} \leq M$ であることを数学的帰納法で示す。
$i = 0$ のとき、 $M$ の定義より明らか。
$i > 0$ のとき、 $s_{i - 1} \leq M$ だと仮定すると、帰納法の仮定と $M$ の定義より、
$\begin{aligned} s_{i} & = \frac{1}{2} (s_{i - 1} - 1 + 2^{t_{i}}) \leq \frac{1}{2} (M - 1 + 2^{t_{i}}) \leq \frac{1}{2} (M + M) = M \\ ∴ s_{i} & \leq M \end{aligned}$
したがって、任意の非負整数 $i$ に対して、 $0 \leq s_{i} \leq M$
これを用いて $S (T, s_{0})$ が周期数列であることを示す。
$S (T, s_{0})$ は有界な非負整数列だから、鳩ノ巣原理より、ある非負整数 $i, j (i < j)$ が存在して、 $s_{i} = s_{j}$ である。
ここで、漸化式を繰り返し用いれば任意の非負整数 $k$ に対して、
$\begin{array}{r} s_{k} = s_{k + (j - i)} \end{array}$
が得られる。これは $j - i$ が $S (T, s_{0})$ の周期の一つであることを表している。 $◻$

定理の証明には直接関係ないが重要なこと

上のジャグリング可能の定義では各サイトスワップ $T$ に対して状態の遷移の仕方が一意に定まることを要請していません。もし、あるサイトスワップに対して異なる複数の状態の遷移が考えられた（つまり、定義の条件を満たす初項 $s_{0}$ が複数存在する）とすると、サイトスワップ $T$ と初項 $s_{0}$ セットでないと（投げる位置を無視した）投げ方を表すことはができません。これに関して、以下の定理が成立します。

ジャグリング可能なサイトスワップ $T$ に対して、 $S (T, s_{0})$ が非負整数列となる初項 $s_{0}$ は一意に定まる。

$S (T, s_{0}) = {s_{i}}_{i = 0}^{\infty}$ と $S (T, s_{0}^{'}) = {s_{i}^{'}}_{i = 0}^{\infty}$ がどちらも非負整数列であるとする。
$\begin{aligned} {\begin{cases} s_{i} = \frac{1}{2} (s_{i - 1} - 1 + 2^{t_{i}}) \\ s_{i}^{'} = \frac{1}{2} (s_{i - 1}^{'} - 1 + 2^{t_{i}}) \end{cases} & (i = 1, 2, 3, . . .) \end{aligned}$
より、
$\begin{aligned} s_{i} - s_{i}^{'} & = \frac{1}{2} (s_{i - 1} - s_{i - 1}^{'}) \\ ∴ s_{i} - s_{i}^{'} & = \frac{1}{2^{i}} (s_{0} - s_{0}^{'}) \end{aligned}$
$i \to \infty$ で $2^{i} \to \infty$ だから、十分大きい $i \in N$ で
$\begin{aligned} | s_{i} - s_{i}^{'} | & = | \frac{1}{2^{i}} (s_{0} - s_{0}^{'}) | = \frac{1}{2^{i}} | s_{0} - s_{0}^{'} | < 1 \end{aligned}$
${s_{i}}_{i = 0}^{\infty}$ と ${s_{i}^{'}}_{i = 0}^{\infty}$ はともに整数列だから、 $| s_{i} - s_{i}^{'} |$ も整数。
ところで、 $0 \leq | s_{i} - s_{i}^{'} | < 1$ だから、 $| s_{i} - s_{i}^{'} | = 0$
$| s_{i} - s_{i}^{'} | = \frac{1}{2^{i}} | s_{0} - s_{0}^{'} |$ だったから、 $s_{0} = s_{0}^{'}$ $◻$

定理の証明

いよいよ冒頭の定理を証明します。必要性は既に証明しているので、ここでは十分性のみ証明します。

サイトスワップ $T = (t_{1}, t_{2}, . . ., t_{n})$ がジャグリング可能であるためには
条件＊を満たせば十分。

天下り的ですが、
$\begin{array}{r} s_{0} = - 1 + \frac{\sum_{k = 1}^{n} 2^{t_{k} + k - 1}}{2^{n} - 1} \end{array}$ のとき
${s_{i}}_{i = 0}^{\infty} = S (T, s_{0}) \subset Z_{\geq 0}$ であることを示します。
まず $s_{0} \in Z_{\geq 0}$ を示しましょう。
$a \equiv b (\mod n)$ かつ $a \leq b$ のとき、ある非負整数 $c$ が存在して $b = c n + a$ だから、 $2^{b} = (2^{n})^{c} 2^{a} \equiv 1^{c} 2^{a} = 2^{a} (\mod 2^{n} - 1)$ です。
従って、定理の条件より
$\begin{array}{r} \sum_{k = 1}^{n} 2^{t_{k} + k - 1} \equiv \sum_{k = 1}^{n} 2^{k - 1} = 2^{n} - 1 \equiv 0 (\mod 2^{n} - 1) \end{array}$
よって、 $\sum_{k = 1}^{n} 2^{t_{k} + k - 1}$ は $2^{n} - 1$ の倍数です。また明らかに $s_{0} \geq 0$ なので $s_{0} \in Z_{\geq 0}$ です。
漸化式に代入して計算すると、 $s_{1}$ は次のようななります。
$\begin{array}{r} s_{1} = - 1 + \frac{\sum_{k = 1}^{n} 2^{t_{k + 1} + k - 1}}{2^{n} - 1} \end{array}$
同様に計算すると、帰納的に次の式が得られます。
$\begin{array}{r} s_{i} = - 1 + \frac{\sum_{k = 1}^{n} 2^{t_{k + i} + k - 1}}{2^{n} - 1} \end{array}$
$s_{0} \in Z_{\geq 0}$ と全く同様に $s_{i} \in Z_{\geq 0}$ が導かれます。
従って、 $S (T, s_{0}) \subset Z_{\geq 0}$ です。
ゆえに $i \neq j$ かつ $1 \leq i, j \leq n$ なる任意の $i, j$ に対して
$\begin{array}{r} i + t_{i} ≢ j + t_{j} (\mod n) \end{array}$
ならば $T$ はジャグリング可能となります。 $◻$

おわりに

この記事ではトスジャグリングの投げ方を表す方法であるサイトスワップの、特にバニラサイトスワップに関する基礎的な定理を状態という概念を用いて証明しました。
最後の証明に出てきた $s_{0} = - 1 + \frac{\sum_{k = 1}^{n} 2^{t_{k} + k - 1}}{2^{n} - 1}$ という式はサイトスワップ $T$ の状態を計算する公式となっています。
実はジャグリング可能なサイトスワップ $T$ から投げる物体の個数を計算することもできるんですが、これについては気が向けば記事を書こうと思います。
最後まで読んでくださりありがとうございました。