アカウント名:
パスワード:
紙を、特定の人にのみ見せることができるのなら。教授たちを円形に並べて。
1. 最初に鉛筆を持った教授が、ランダムな数字(正でも負でもよい。覚えておくこと)と自分の給料の和を紙に記述し、右の教授に渡す。
2. 紙を受け取った教授は、自分の紙に、受け取った紙に書かれた数字と自分の給料の和を紙に記述し、右の教授に渡す。これを、最初に鉛筆を持った教授のところに紙が回るまで繰り返す
3. 最初に数字を書いた教授は、平均値を計算できる。平均値を計算し、それを宣言する
たとえば、最初の教授が乱数+給与としてこう書いてきたらどうでしょう?
1,000,000,000,000,000
三人目の教授は明らかに不自然な数字から二人目の教授の給料を推測することができます。
つまり、一人目の教授が「何かを知る」チャンスは有りませんが、それ以外の n-1 人の教授の中の誰かの給与を、他の誰かに教えることが可能になります。何しろn人の教授は全員嫉妬深いので、3人目の教授は2人目の教授に対して嫉妬の炎を燃やし、それが「n人の教授 殺人事件」へと…
そうして、二人目と三人目の教授がいなくなった今、ただひとり残った一人目の教授はめでたく、その大学で唯一残った数学教授として、支配権を振るうことに…。
.
というわけで。おそらく全教授が「対称型になるように」処理を組んであげないと危険なのではないかと思います。
なるほど。その発想はなかった。それは面白いです。
うん。それはいけると思う。
普通にこの方法を尊守するなら、自分の給料は漏洩しないが他人の給料も判らない。他人の給料をどうにかして解るように小細工しようとすると、自分の給料が露呈する。
------
たとえば3人の場合
最初に分かっている数字(乱数は予め決めておくとする)(給料をX1,X2,X3、乱数を R1, R2, R3 とする)1] X1, R12] X2, R23] X3, R3 一巡目 受け取る数字 | 書いた数字----------------+--------------1] 0 | R1+X12] R1+X1 | R1+R2+X1+X23] R1+R2+X1+X2 | R1+R2+R3+X1+X2+X3 二巡目 受け取る数字 | 書いた数字---------------------+--------------1] R1+R2+R3+X1+X2+X3 | R2+R3+X1+X2+X32] R2+R3+X1+X2+X3 | R3+X1+X2+X33] R3+X1+X2+X3 | X1+X2+X3 ここで公開される数字: X1+X2+X3 この結果解る数字 (各自自分の数字以外で解る組み合わせ)1] X2+X3, R2+R32] X1+X3, R3, R1-X33] X1+X2, R1+R2 1はR1を典型的な数字にすることで 2 に X3 を伝えることは可能だ(R1-X3)。しかし、その瞬間X1もバレてしまう(R1+X1)。だから 1 は R1 を典型的な値にできない。 2はどう裏切っても、自分の数字を危険にさらすだけだ。 3はどう裏切っても、自分の数字を危機にさらすだけだ。
よって、1,2,3 は裏切り行為を働けない。
1順目に、最後に記述する教授が1,000,000,000,000,000とやっちゃったとき、2順目に、最初の教授が引き算する乱数を2番めの教授が見抜いてしまわないでしょうか。
あー、これは…
3人だと、教授2にR1が露呈すると、自動的にX1が露呈する。でもそうするとX3も教授2に露呈するので、教授3は裏切れない。
ところが、4人以上の n人の場合、R1の推定からX1は露呈するが、それ以外の乱数はΣ(i=3..n)Ri、給料もΣ(i=3..n)Xi の形でしか教授2には露呈しない。めでたく教授nは教授2に、教授1の情報を開示しつつ、教授2に対しては自分の給料は隠し通すことができる…。
教授n-1はどうだろう? 教授n-1は2周目で Rn+ΣXi を知ることができる。あとで ΣXi は判るので Rn は判る。当然Rn-1は知っている。1周目に Σ(i=1..n-2)(Ri+Xi) を知っているので、最後にΣXi が判った途端、Σ(i=1..n-2)(Ri) - Xn を知ることができる。でも、ΣRi を求める事が出来ないので、教授nが裏切った事を知る事が出来ない。教授nが裏切った事が判ればΣRi から Σ(i=1..n-2)Ri が判るので Xn が判るのに。
なるほど。4人以上だと「最後の教授」が裏切る事が出来ますね。どうやら「1周目」から「2周目」に切り替わる境界が判るのが問題の発生源のようだ。私の考えが浅かったか…。
となると、やはり乱数は紙に書いてかき集める以外手が無いのか??
・教授たちは、自分の直前に書いた教授が乱数を発生させていた場合、紙を突き返して乱数を変えさせる権利を持つ・紙に、新しい数字を書く余地がなくなったら、その時点で紙を回すのを終了し、教授たちは平均値を知ることができなくなる
というルールを加えてみてはどうでしょうか。教授たちがみな、平均値を知りたいと思っているなら、紙に余地がなくなる前に意地悪をやめるはずなのですが、このルールを加えることで、意図的に終了させて得する教授がいないかを考える必要は出てきます。とりあえず、私には見当たりませんでしたが…
それは駄目でしょう。有限ステップのアルゴリズムにならない。
紙に十分な余地があればこのアルゴリズムでは無限ステップになってしまいます。確かに「紙が無くなったら終了」は現実的な「実装方法」ではありますが、この手の謎々は本来「アルゴリズム的に有限ステップで解決する事が保障される方法を見つけろ」という条件が背後にあるものなので…
ちょっと謎々の答としてずる過ぎるのではないかと。
この「突き返す」という行為は、確かに自分にとって不利な数字を排除するためにも使えますが、自分にとって有利な数字になるまで retry を繰り返させる、という形でも使えます。また、無意味に突き返すことで「突き返された人を貶める」事にも使えます。
こうなると、最初の二人の間で政治的な取引が始まってしまい、何が何やら…。
乱数を加えた結果を露骨な数字にするというのは、「内密チャンネル」という考え方の一種です。内密チャンネルを使って、本来伝達できない情報を、他の人に露呈しないように伝達する(そのチャンネルを通して伝わる情報は、必ずしも内密チャンネルを作った人が知っている必要性はありません)。
全教授が「内密チャンネルの発生の可能性について」疑うなら、そのアルゴリズムはそもそも採用されないでしょう。
私の例は「判りやすい数字」を用いた内密チャンネルだったので事前共謀は必要ありませんでした。しかし、一般に「自分以外の二人の教授の共謀」を知る事はできません。ということはどのような数字を渡されてもそれが「共謀によって作られた数字ではない」事を知る術はないわけです。こうなると、何を渡されても拒否するしか手が無くなります。
ここで、1順目にある教授がある数字を受け取って、それに自分の乱数と給料を足して、次の教授に渡したとします。この教授はどうやって、渡された数字が誰かが共謀して作った数字ではない事を知ったのでしょう?あり得る唯一の答は、その数字が自分と誰かが共謀して作った数字だった場合ではないでしょうか??
こう考えると、もっと根源的に「全ての教授たちは共謀しない」という前提を置かない限り、この追加条件は何も保証しない事になります…
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
物事のやり方は一つではない -- Perlな人
ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
紙を、特定の人にのみ見せることができるのなら。
教授たちを円形に並べて。
1. 最初に鉛筆を持った教授が、ランダムな数字(正でも負でもよい。覚えておくこと)と自分の給料の和を紙に記述し、右の教授に渡す。
2. 紙を受け取った教授は、自分の紙に、受け取った紙に書かれた数字と自分の給料の和を紙に記述し、右の教授に渡す。これを、最初に鉛筆を持った教授のところに紙が回るまで繰り返す
3. 最初に数字を書いた教授は、平均値を計算できる。平均値を計算し、それを宣言する
1を聞いて0を知れ!
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
たとえば、最初の教授が乱数+給与としてこう書いてきたらどうでしょう?
三人目の教授は明らかに不自然な数字から二人目の教授の給料を推測することができます。
つまり、一人目の教授が「何かを知る」チャンスは有りませんが、それ以外の n-1 人の教授の中の誰かの給与を、他の誰かに教えることが可能になります。何しろn人の教授は全員嫉妬深いので、3人目の教授は2人目の教授に対して嫉妬の炎を燃やし、それが「n人の教授 殺人事件」へと…
そうして、二人目と三人目の教授がいなくなった今、ただひとり残った一人目の教授はめでたく、その大学で唯一残った数学教授として、支配権を振るうことに…。
.
というわけで。おそらく全教授が「対称型になるように」処理を組んであげないと危険なのではないかと思います。
fjの教祖様
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
なるほど。その発想はなかった。それは面白いです。
1を聞いて0を知れ!
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
1. 最初に鉛筆を持った教授が、自分で決めたランダムな値＋自分の給料 を、"隣の教授" の紙に記述する。
2．自分が持っている紙に記述された教授は、紙に記述された値＋自分で決めたランダムな値＋自分の給料 を、
"隣の教授" の紙に記述する。これを最初に記述した教授に戻るまで繰り返す。
3. 最初に記述した教授に戻ったら、紙に記述された値－ランダムな値を、"隣の教授" の紙に記述する。
2. と同じように最初に記述した教授に戻るまで繰り返す。
4．最初に記述した教授の紙に記述された値が、全員の給料の合計。あとは人数で割ると。
これならどうでしょう？
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
うん。それはいけると思う。
普通にこの方法を尊守するなら、自分の給料は漏洩しないが他人の給料も判らない。
他人の給料をどうにかして解るように小細工しようとすると、自分の給料が露呈する。
------
たとえば3人の場合
よって、1,2,3 は裏切り行為を働けない。
fjの教祖様
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
1順目に、最後に記述する教授が
1,000,000,000,000,000
とやっちゃったとき、
2順目に、最初の教授が引き算する乱数を
2番めの教授が見抜いてしまわないでしょうか。
1を聞いて0を知れ!
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
あー、これは…
.
3人だと、教授2にR1が露呈すると、自動的にX1が露呈する。でもそうするとX3も教授2に露呈するので、教授3は裏切れない。
.
ところが、4人以上の n人の場合、R1の推定からX1は露呈するが、それ以外の乱数はΣ(i=3..n)Ri、給料もΣ(i=3..n)Xi の形でしか教授2には露呈しない。めでたく教授nは教授2に、教授1の情報を開示しつつ、教授2に対しては自分の給料は隠し通すことができる…。
教授n-1はどうだろう? 教授n-1は2周目で Rn+ΣXi を知ることができる。あとで ΣXi は判るので Rn は判る。当然Rn-1は知っている。
1周目に Σ(i=1..n-2)(Ri+Xi) を知っているので、最後にΣXi が判った途端、Σ(i=1..n-2)(Ri) - Xn を知ることができる。でも、ΣRi を求める事が出来ないので、教授nが裏切った事を知る事が出来ない。教授nが裏切った事が判ればΣRi から Σ(i=1..n-2)Ri が判るので Xn が判るのに。
.
なるほど。4人以上だと「最後の教授」が裏切る事が出来ますね。どうやら「1周目」から「2周目」に切り替わる境界が判るのが問題の発生源のようだ。私の考えが浅かったか…。
となると、やはり乱数は紙に書いてかき集める以外手が無いのか??
fjの教祖様
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
・教授たちは、自分の直前に書いた教授が乱数を発生させていた場合、紙を突き返して乱数を変えさせる権利を持つ
・紙に、新しい数字を書く余地がなくなったら、その時点で紙を回すのを終了し、教授たちは平均値を知ることができなくなる
というルールを加えてみてはどうでしょうか。
教授たちがみな、平均値を知りたいと思っているなら、紙に余地がなくなる前に意地悪をやめるはずなのですが、
このルールを加えることで、意図的に終了させて得する教授がいないかを考える必要は出てきます。
とりあえず、私には見当たりませんでしたが…
1を聞いて0を知れ!
Re:ランダムな数字って、ひとつじゃダメですか？ (スコア:1)
それは駄目でしょう。有限ステップのアルゴリズムにならない。
紙に十分な余地があればこのアルゴリズムでは無限ステップになってしまいます。確かに「紙が無くなったら終了」は現実的な「実装方法」ではありますが、この手の謎々は本来
「アルゴリズム的に有限ステップで解決する事が保障される方法を見つけろ」
という条件が背後にあるものなので…
ちょっと謎々の答としてずる過ぎるのではないかと。
.
この「突き返す」という行為は、確かに自分にとって不利な数字を排除するためにも使えますが、自分にとって有利な数字になるまで retry を繰り返させる、という形でも使えます。また、無意味に突き返すことで「突き返された人を貶める」事にも使えます。
こうなると、最初の二人の間で政治的な取引が始まってしまい、何が何やら…。
.
乱数を加えた結果を露骨な数字にするというのは、「内密チャンネル」という考え方の一種です。内密チャンネルを使って、本来伝達できない情報を、他の人に露呈しないように伝達する(そのチャンネルを通して伝わる情報は、必ずしも内密チャンネルを作った人が知っている必要性はありません)。
全教授が「内密チャンネルの発生の可能性について」疑うなら、そのアルゴリズムはそもそも採用されないでしょう。
私の例は「判りやすい数字」を用いた内密チャンネルだったので事前共謀は必要ありませんでした。しかし、一般に「自分以外の二人の教授の共謀」を知る事はできません。ということはどのような数字を渡されてもそれが「共謀によって作られた数字ではない」事を知る術はないわけです。こうなると、何を渡されても拒否するしか手が無くなります。
ここで、1順目にある教授がある数字を受け取って、それに自分の乱数と給料を足して、次の教授に渡したとします。この教授はどうやって、渡された数字が誰かが共謀して作った数字ではない事を知ったのでしょう?
あり得る唯一の答は、その数字が自分と誰かが共謀して作った数字だった場合ではないでしょうか??
こう考えると、もっと根源的に「全ての教授たちは共謀しない」という前提を置かない限り、この追加条件は何も保証しない事になります…
fjの教祖様