サイトスワップにまつわる 2 つの事実の証明を書いてみました。
(以前 NIFTY の FMAGIC に書いたものの転載)
なるべく易しめに具体例を使って書いたつもりです。
が、数学の得意な人には、式を使って書いたほうがわかりやすいのでしょう :-)
わかりにくい箇所や質問などありましたら、お気軽にどうぞ。
(emda@po.jah.ne.jp)
----------------------------------------------------------------------
(*) サイトスワップで A1, A2,..., An というパターンがジャグリング可能で
あるための条件は、1+A1, 2+A2, ..., n+An を n で割った余りが異なること
である。
(**) そのとき、ボールの個数は、( A1 + A2 + A3 + ... + An ) / n である。
----------
わかりやすくするために、具体的に 4 7 1 というパターンで説明します。
「4+1=5, 7+2=9, 1+3=4 を 3 で割った余り 2,0,1 は異なるから、可能」
というのを示すわけです。
+--------------------++-++-----
| +--++----------+ || ||
| | v| v v| v|
4 7 1 4 7 1 4 7 1 4 7 1 ...
| ^| | ^| ^ ^|
| || +--++----------+ ||
+-----------++-------------------++--
と進んでいきますが、横一列に並べる代わりに、これを
1 2 3 (列目)
行 -----------
1 | 4 7 1
2 | 4 7 1
3 | 4 7 1
...
と3個ずつ区切って、縦に書きます。
1列目にある「4」が次にどこに行くかというと、4つ先、(次の行の)2列目の
「7」です。
2列目の「7」は、(次の次の行の)3列目の「1」、
3列目の「1」は、(次の行の)1列目の「4」です。
(紙に上の表を書いて、行き先の数字を矢印で結んでみてください)
このように、
1列目(4) → 2列目(7)
2列目(7) → 3列目(1)
3列目(1) → 1列目(4)
となっていて、(ジャグリング可能なパターンならば = ボールがぶつからない
ならば) 列ごとに行き先はすべて違う列になります。
それはなぜか---
もしも、ある列に違う2つの列から進んできたとします。
例えば左図のように、
a B A が◎に、B が ○に進むとします。
a ○ b すると、B の2つ下の b は、当然◎に進むことになり、
A b これではボールがぶつかるので、ジャグリング可能な
a ◎ b ことに反します。
したがって、行き先はすべて違う列です。
4 7 1 の場合、1列目,2列目,3列目それぞれの行き先の列は、
1+4, 2+7, 3+1 を 3 で割った余りです:
1+4 = 5 → 2 列目
2+7 = 9 → 0(3) 列目 (余り0は3列目を表す)
3+1 = 4 → 1 列目
つまり、列ごとに違う列に進むということは、最初に書いた (*) の条件を
表すわけです。
逆に「列ごとに違う列に進む」ならジャグリング可能であることは、簡単です。
違う列に進むなら、ボールの行き先がぶつかることはないからです。
----------
[ ボールの個数が (A1+A2+...+An)/n であることの証明 ]
上に書いたように、3 個ずつ縦に並べて、行き先へ矢印を書き込んだ表を考えま
す。1個のボールの軌跡は、矢印を次々につないだものだから、ボールの個数
は、軌跡のスタート地点を数えればわかります。
ここで、スタート地点というのは、「そこに向かう矢印がない地点」だと言え
ます。
表を見てみます。1行目の 4,7,1 が進むところを７,１,４で表しました。
1 2 3 (列目) 2行目以降の 4,7,1 から伸びる矢印は、その
行 ------------ ７,１,４ の下に続きます。ということは、
1 | 4 7 1 「そこに向かう矢印がない地点」というのは、
2 | ４ ７ 1 ７,１,４ よりも上の地点です。
3 | 4 7 １ この場合は、4個(4,7,1,1)なので、ボールは4個
... だとわかります。実際、(4+7+1)/3 = 4 です。
一般にその「4 個」をどう数えるかが問題です。
それには、７,１,４ のそれぞれの上に何個あるかを数えて、合計します。
たとえば ７ は、初めの 4 から数えて 1+4=5 番目の数です。
７ は2列目の数だから、７の上には (5-2)/3 = 1 行、つまり(同じ列の)
７ の上には 1個 あります。
１ は、2+7 = 9 番目の数。3列目の数だから、(9-3)/3 = 2 個
４ は、3+1 = 4 番目の数。1列目の数だから、(4-1)/3 = 1 個
したがって、合計 1+2+1 = 4 個です。
さて、一般化するには、次のように考えます。７,１,４ は、初めから数えて
1+4, 2+7, 3+1
番目の数で、それぞれから 2,3,1 を引いて 3 で割った合計がボールの個数です。
それは
(1+4 - 2)/3 + (2+7 - 3)/3 + (3+1 - 1)/3
o x o x o x
という計算でしたが、o のところに 1,2,3 があって、x のところにも
1,2,3 がある(何列目かを表すから、1,2,3 の順番を変えただけ)ので、結局
{ (1+4) + (2+7) + (3+1) - 2 - 3 - 1 }/3
= (4 + 7 + 1)/3
という計算になります。これを一般に言うと、
{ (1+A1) + (2+A2) + (3+A3) + ... + (n+An) - 1 - 2 - 3 - ... - n }/n
= ( A1 + A2 + A3 + ... + An ) / n
となります。