まず、サイコロが6個の場合を考えてみます。
王様が動かすサイコロは1番から6番の6種類。
議論がしやすくなるようにサイコロの番号をつけかえて、0番,1番,2番,3番,4番,5番とします。
Bは6個のサイコロの目の状態から王様の選んだサイコロの番号(0,1,2,3,4,5)が特定できればよいです。
サイコロの目の数を並べると6桁の数と考えることができます。
6桁の数を0～5のいずれかと対応させるには、6で割った余りを考えればいいですね。
王様の選んだサイコロがn番だったときは、6桁の数字を6で割った余りがnになるようにサイコロを動かせばいいです。
が、これはうまくいきません。
1の位にあたるサイコロを動かした場合、6桁の数字は1増えます。
10の位にあたるサイコロを動かした場合、6桁の数字は10増えます。余りは4増えたときと同じです。
100の位にあたるサイコロを動かした場合、6桁の数字は100増えます。余りは4増えたときと同じです。
異なるサイコロを動かしても余りが同じになってしまうことがあるのです。
王様の選ぶサイコロは6種類ですから、余りも6種類できないといけません。
6個の目から一つの数を作りだすという発想はよかったですが、作り方がまずかったです。
0,1,2,3,4,5番のサイコロを動かしたときに余りもそれぞれ0,1,2,3,4,5だけ増えるようになればいいのです。
k番のサイコロの目をd(k)としたとき、Σ｛k*d(k)｝を考えればうまくいきます。
これを6で割ったときの余りを評価値と呼ぶことにしましょう。
余りは6種類ですので、0,1,2,3,4,5のいずれかを足すことにより、任意の評価値にすることが可能です。
評価値が王様の選んだサイコロの番号に一致するようにサイコロを動かせばよいのです。
Aはサイコロが振られた後で評価値を計算。これをmとします。
王様が選んだサイコロの番号をnとします。
Aは(n-m)を6で割った余りを計算します。
(n-m)が6未満の場合は6を足して計算すればよいです。
Aは、その余りと一致する番号のサイコロを動かします。
すると、その時点での評価値はnになります。
Bは伝えられたサイコロの目を基に評価値を計算します。
その番号のサイコロが王様の選んだものだと答えれば勝ちです。
サイコロが10個の場合も同様に考えてみましょう。
10個のサイコロの番号を0,1,2,・・・,9とします。
k番のサイコロの目をd(k)としたとき、Σ｛k*d(k)｝を10で割った余りを評価値とします。
n番のサイコロの目が1増えると、n*d(n)はn増えますのでよさげですが、これでは駄目です。
なぜかというと、動かすサイコロの目が6の場合は1に変化させることになるからです。
サイコロが6個の場合は6で割った余りを考えましたので、+1も-5も評価値に影響はありませんでした。
ところが、10個の場合は-5は+5と同じであり、同じサイコロを動かしても評価値の変化が異なるのです。
余りを使う方法ではうまくいかないようです。
他の計算方法を使えば10個の場合でもいけると思われるかもしれませんが、実はうまくいくことはありません。
なぜうまくいかないのか説明しましょう。
最初のサイコロの目の状態を初期配置、Aがサイコロを動かした後の状態を最終配置とします。
Bは最終配置の情報から必ず王様の選んだサイコロが特定できると仮定します。
初期配置の総数は6^10個。
ある初期配置に対して王様の選択が異なればAが動かすサイコロも異なります。
一つの初期配置に対して10個のサイコロをそれぞれ動かしてできる最終配置10個が対応します。
初期配置と王様の選んだサイコロが決まれば最終配置は一意に決まります。
最終配置としてすべての組み合わせが現れますので最終配置の総数も6^10個です。
一つの最終配置に対応する初期配置は10個です。
最終配置から王様の選んだサイコロが特定できますので、最終配置とそのサイコロ番号が対応します。
サイコロは10個ですが最終配置の総数は10の倍数ではないため、
対応する最終配置の数が(6^10)/10より大きくなるサイコロ番号kが存在します。
kに対応する最終配置になる初期配置に重複がないと、初期配置の総数が6^10を超えてしまいますので、
初期配置に重複があることになります。
これは、初期配置と王様の選んだサイコロが同じでも最終配置が異なることがあるということで、矛盾です。
よって、仮定は誤りであり、必ず王様の選んだサイコロが特定できるとは限らないのです。
6の次には1になるという条件がありますので、サイコロの個数に制約があるのです。
ちなみに、この条件がなければ個数に制約はなくなります。
例えば、王様が適当に10個の自然数を書いて、その中から無作為に一つ選ぶとします。
Bは10個の自然数の中から一つを選んで1大きい数に書き換える、という場合。
k番の自然数をd(k)としたとき、Σ｛k*d(k)｝を10で割った余りを評価値とすればうまくいきます。
他の個数でも問題ありません。
6の次に1になるということは+1と-5という操作に同じ意味を持たせなくてはいけません。
1と-5を同一視するということは0と6を同一視するということです。
6で割った余りを考えればうまくいくことは確認済です。
6の約数の場合もうまくいきます。
1個の場合は明らかですが、2個、3個の場合にも6個の場合と同様の方法でうまくいきます。
では、7個以上の場合は不可能なのでしょうか。
いえいえ。7個以上でも可能な場合があります。
例えば36個。
36で割った余りを考えるとうまくいきませんが、ベクトルで考えるとうまくいくのです。
36は6×6ですので、x,yを0以上5以下の整数として、(x,y)というベクトルを考えます。
36個のサイコロにこのベクトルを対応させます。
(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),・・・,(5,4),(5,5)
という順にします。
xyを2桁の6進数と考えると(10進数の)0～35に対応します。
k番目のサイコロのベクトルをv(k)としましょう。
指標値として、Σ｛d(k)*v(k)｝の各成分を6で割った余りのベクトルを考えます。
v(k)=(x,y)のとき、
k番のサイコロの目を1増やすと、指標値に(x,y)が加算されます。
k番のサイコロの目を5減らすと、指標値に(-5x,-5y)が加算されます。
(x,y)-(-5x,-5y)=(6x,6y)で、各成分は6で割った余りになりますので、
二つの指標値の差は(0,0)。
つまり一致しています。
計算するのがベクトルになるだけで、6個の場合と同じやり方です。
Aはサイコロが振られた後で評価値のベクトルを計算。
王様が選んだサイコロのベクトルからそれを引いて動かすサイコロのベクトルを求めます。
(各成分の和や差を6で割った余りを計算します)
Bは伝えられたサイコロの目を基に評価値を計算し、
そのベクトルの番号のサイコロを答えとすればよいです。
ベクトルは二次元に限る必要はありません。
6×6×6個のサイコロに(x,y,z)と三次元ベクトルを割り当ててもいけますし、
好きなだけ次元を大きくすることができます。
6の累乗でなくても2と3のみを含む積であれば可能です。
2×2個の場合はx,yを0,1として、(x,y)というベクトルを考えます。
この場合はベクトルの計算時に各成分を2で割った余りとします。
サイコロの個数の素因数に2,3以外がなければいつでも可能です。
逆に、2,3以外の素因数を含む場合は、
配置の総数がサイコロの個数の倍数にならないため不可能です。
この問題の場合、条件を満たす個数で最も小さい個数は12個ですので、
サイコロ12個を使うのが一番楽でしょう。
2×6で二次元ベクトルで計算してもいいですし、2×2×3の三次元ベクトルでもOKです。
余談ですが、サイコロの個数が2の累乗の場合、
ベクトルの各成分は2で割った余りの0か1です。
サイコロは6面ですが、2値しか使わないため、表裏の2面とみなすことができます。
サイコロではなくコインを使った問題に変換できます。
例えば、王様が16枚のコインを(表裏は適当に)並べて、その中の一枚を選びます。
Aはコインの一枚をひっくり返し、Bは王様の選んだコインを当てるというゲーム。
16=2^4ですので、4次元のベクトルを考えて指標値を計算すればよいです。
各成分の計算では足し算も引き算も同じ結果になります。
すべての計算は足し算で行えます。
コインの問題は何かの本で見まして、私がサイコロを使った問題に発展させました。
コインについては排他的論理和を計算すると書いてありました。
排他的論理和ってなんか難しそうな響きですが、要は繰上りのない足し算なんですね。
0+0=0
0+1=1
1+0=1
1+1=0
サイコロ問題を考察したことによって、排他的論理和が覚えられました(笑)。
0 件のコメント:
コメントを投稿