電話でジャンケンする方法

以下のような方法があります。

1. Aさんは最初に非常に大きい素数を二つ選んで、これを掛け合わせます。 そして『この掛け合わせた数「123…」の元になった数の小さい方の上 から4桁目は奇数か偶数か？』と聞きます。
2. Bさんはどちらかを答えます。
3. Bさんが当たっていればBさんの勝ちで、Bさんが外れていれば、 Aさんの勝ちです。
4. Aさんは最初に選んだ大きい素数をBさんに教えてあげます。 この時点でBさんは自分が買ったかどうか、自分で判断できます。

これがどうして公平になるんでしょう？まずBさんがイカサマをしようと思っ ても、これは無理です。2番目のステップでBさんが必ず正解を答えるには、 Aさんが教えてくれた数を素因数分解しなければならず、これには数十万年か かるからです。逆にAさんがイカサマをしようと思っても、これまた無理です。 なぜなら4番目のステップで、Aさんが最初に選んだ素数をBさんに教えていま すから、もしAさんがイカサマをしていたら、Bさんにそれがばれてしまいます。 結局 2 番目のステップでは B さんはあてずっぽうを答えるしかなく、しかも その勝負がどちらの勝ちになるか、は、両方が納得できる形で確認できるわけ です。不思議ですね…。

Last modified: Mon Nov 25 14:15:16 EST 2002 by R.Uehara (uehara@jaist.ac.jp)