1. ジャグリング可能性の判別テストの妥当性を証明しなさい。

まずこのテストに合格しなければジャグリング不可能であることは明らかです。チェックがブッキングしてしまうことはその地点に同時にやってくるボールが存在する事を意味しているからです。

これは実は1のテストを行っているに過ぎません。いま数列を

A1,A2,A3,…An

とします。

この数列に左から順番に0,1,2,3,…,n-1という番号を付けておきます。（これをIndexということにします。）

Akという数字について上のテストを行うとチェックはどこのIndexにいくことになるのでしょう。Akから右にAk個カウントしていきます。AkのIndexはk-1ですから行く先のIndexは

(k-1)+Akをnで割った余り

となるはずです。合同式を使って書けば

(k-1)+Ak ≡（行く先のIndex）(mod n)

これは合同式を使って証明しておきましょう。サイトスワップの法則2から

(k-1)+Ak (mod n) (k=1,2,…,n)

の値は全て異なります。つまり0〜n-1までの全ての数字が現れるということです。よってこれらを全て加えた和を考えると

A1＋(1+A2)+(2+A3)+…+(n-1+An) ≡ 0+1+2+3+…+(n-1) (mod n)

整理すると

A1+A2+…+An ≡　0 (mod n)

これはA1,A2,…,Anの和がnで割り切れる事、つまり平均が整数になる事を示しています。

これは(簡単そうで）案外難しい問題です。 ここでは軌道分解を用いて、この法則を証明しておきます。

たった一つの軌道からなるパターンについてこの法則を証明しましょう。 一般的に証明しようとなると複雑になるので実例をあげて見ていきます。

４４１はたった一つの軌道からなります。1つのボールの投げられ方に注目すると

４→→→４→→→１

と投げられています。（矢印はボールが空中にある時間です。）全てのボールはこの軌道の中を動いている事になります。この中のボールの個数が分かればこのパターンで必要なボールの数がわかるのですがこれは次のような発想を使います。

まずこの軌道の長さは

４＋４＋１　＝　９

です。ですから1つのボールは9ビートで軌道を一周します。ここで1つのボールの投げ方(例えば最初の４）に注目するとこの投げ方は何ビートごとに行われているのでしょうか。数列の長さが３ですからこの投げ方が行われるのは当然3ビートごとということになります。以上の事からこのパターンの中に存在するボールの個数は

９÷３＝３

ということが分かるのです。ここでやった事は数列の全ての数字を足して（軌道の長さを求める事に相当）数列の長さで割ったのですから、平均を求めているに他なりません。よってこの定理は証明されました。

このアイディアを分かりやすくするため下のようなアニメーションを作ってみました。

一般的な(軌道が1つとは限らない）パターンについてこの定理を証明しようと思ったらパターンを軌道に分解すればいいのです。それぞれの軌道では上の事実が使えるのですから、ボールの個数はその軌道を表す数列の平均を計算する事で求める事ができます。それを最後に全て足し算します。ところがそれぞれの軌道の数列の長さは元のパターンの数列の長さに等しいのですから、先に全ての数字を足し算しておいてそれを数列の長さで割っても同じことです。これはもとの数列の平均を求める事に他なりません。

これも具体的な例で説明することにしましょう。

例えば５３４は

５０４　０３０

と分解できます。

それぞれの軌道に含まれるボールの個数を求める式は

(５＋０＋４）÷３

(０＋３＋０）÷３

です。この結果を加えればパターンのボールの個数が分かるのですがそれは

(５＋３＋４）÷３

をすることと同じです。つまり数列の平均がボールの個数になると言うわけです。

下のアニメーションを見てください。軌道の中をボールが循環している様子が良く分かります。

サイトスワップの法則2を考えれば明らかです。 なぜならある数字にnを足したり,引いたりしてもその数字をnで割った余りは変わらないからです。式で書けば

A≡A±ｎ　(mod n)

です。