同じ重さの石が一つもない10個の石を考える。それぞれの重さを例えば
X(0) = 125(g)としよう。
さて、この時にこの10個の石を適当に選んである重さの塊を作った。 この重さからどの石を使ったのか見つけるにはどうすればよいか。
魔法の数字を２つ考えます。その２つを P, Q とします。 P, Q は次の条件を満たすようにします。
条件１：P, Q は共に素数である。さらに、魔法の数字から別の数字 Y を求めます。 Y は『P×Y + Q×Z = 1』となるような数字で、 Y, Z は整数とします。 この時、次のような魔法の現象が起きるのだそうです。
『P, Q を適切に選んでやる。で、次のような変換をする：
x(0) = ( X(0)×Y ) % Qそうすると、あら不思議、x(i) は常に x(0) 〜 x(i-1) までの総合計よりも 大きな数字になる、そんな P, Q の組が必ず存在する。こいつはさらに、
X(0) = ( x(0)×P ) % Qを満たす。 しかも、
x(2)+x(5)+x(7) = (( X(2)+X(5)+X(7) )×Y ) % Qのように石をそれぞれ足してやった結果は、変換の後もちゃんと成立する。』
一体そんなことの何がいいのか。
仮に魔法の数字、P, Q, と Y が見つかったとしよう。 で、全部変換したとしよう。
この時仮に ( X(2)+X(5)+X(7) ) から 2, 5, 7 を答える必要があるとしよう。 当然( X(2)+X(5)+X(7) ) を変換すると ある魔法の数字 ( x(2)+x(5)+x(7) ) が出来る。
さて、この数字、 x(i) の持っている特徴から『x(8) よりは小さい』数字にしかならないのだ。 つまり「8と9は絶対答の中に入らない」ことがわかる。
さらにこの数字、必ず『x(7)よりは大きい』数字になる。 もし X(7), X(8), X(9) を含んでいなければ、 この数字は X(7) よりも必ず小さくなることが条件からわかっているからだ。
ということはこの塊は、必ず「7」を含んでいることがわかる。
次にこの「変換後の数字」から x(7) を引く。 すると、今度はこの残った数字が x(5) と x(6) の間の数字であることがわかり、 そこから必ず「5」を含んでいることがわかる。
同様にすると結局最後まで全部求めることができ、 どの石が使われているかが全部わかるのだ。
たぶん、ここまでの段階で何となくわかっる人はわかると思うが、 この方法には激しい弱点がある。 P, Q を見つけるのがとんでもなく面倒なのだ。
上の例は P = 6123, Q = 2999, Y = 24 とすると
x(0) = 1となる。
なるけれども、求めるのがたった１通りならば P, Q を求めるよりも総当たりをかけた方が圧倒的にはやい。 しかも、P は X() の個数が大きくなるとそれだけでどんどん大きくなる。 当たり前と言えば当たり前だが。
従って、複数の組合せに関して求める場合は良いかも知れないが、 そうじゃない場合はこの方法が良いとは限らない(悪いとも限らないが)。
でも、この方法、魔法を使ってるみたいでかっこいいよね。