okkyの日記： 「エレガントな問題解決」の解答が判らない 41
うーむ。「エレガントな問題解決」の答が判らない～。
解答集が無いので、解けたんだかどうだか判らない問題が永久の謎になってしまう。
数学コンテストで出された問題：
from p.10
1.3.11 (ロシア 1995)以下の方程式を解け.
cos(cos(cos(cos x))) = sin(sin(sin(sin x)))
こう言うのが難しいのは、まぁいいとして (あまり嬉しくないが)。
次のような問題が解けたんだか解けてないんだかわからないのは悔しい。
from p.28
2.1.21 嫉妬深い教授たちが1部屋に閉じ込められている。鉛筆と、1人に1枚の小さな紙切れがあるが、その他には何も無い。教授たちは、給料の平均値(中央値ではない)を知りたいと思っている。仲間たちに比べて、自分の状況が満足のいくものであるか、不本意なものであるかを知りたいのである。しかし、彼らは秘密主義者でもあって、自分の給料の情報は、他の誰にも知られたくないと思っている。どの教授も、自分の給料についての情報以外の情報は何も得ずに、全員の給料の平均額を求めることができるだろうか。例えば、「3人は40,000取る以上稼いでいる」とか「90,000ドル以上稼いでいる者はいない」などの情報も得られない。
.
とりあえず私が考えたのはこうだ。
まず各教授に、ランダムな数字を1つ考えてもらう。給料に比べて馬鹿でかいと良い。1とか2とかはやめておくように。
で、その数字を紙に書いてもらう。次に、自分のほんとうの給料にこのランダムな数字を加えたものを順番に申請してもらい、足しあわせていく。----(1)
一方で紙を回収してよく混ぜ、どれが誰のものだか判らないようにする。
で、紙に書かれた数字を全部足しあわせる。 ----(2)
(1) - (2) を行い、人数で割ると、平均値が出る。当たり前だがいくつか制約条件がある。
・教授の数は3人以上である。2人では平均値と自分の給料から相手の給料が判る。1人では問題にならない。0人では教授がいない。
・教授は嘘はつかないとする。嘘をつかれたら問題が成立しなくなる。例えば、本当の給料の代わりにランダムな値を申告して、自分の給与を知られずに他人の給料を知りたいと考えたりはしない、とする。全員がこれをやるとただの乱数の平均値になってしまう。
・各教授は単純な加減乗除で間違えないとする。多分、数学教授の多くは単純な加減乗除は久しくやっていないに違いない。ここを間違えられるとどうしようもない。
多分合ってるんじゃないかと思うが…判らない。
結局、各教授について、給料にランダムな数字を加えた結果とランダムな数字の両方がひもづいてしまったら、その教授の給料はバレてしまう。
もし、紙にランダムな数字を書いてそれを混ぜたら出自が判らなくなるなら、各教授が素直に自分の給料を紙に書いて、それを混ぜても出自が判らなくなりそうなものだ。ならランダムな数字を足したり引いたりするだけ無駄な気もする。
誰か、答が解る人はいないだろうか??
ランダムに分ける案 (スコア:2)
(1) n人の教授がいるとして、各自、自分の給料をnで割る。この数値を全員分足し合わせれば平均値になる。
(2) 各自、(1)の値をさらにいくつかに分割する（等分するのではなく分割するだけ）。ここでは3つに分けることにする。例えばA教授が(1)で得た値が10000であれば、10000=1000+4000+5000とする。
(3) みんなで円座になってすわり、最初のA教授はとりあえずランダムの数字（5000とか）と、(2)で分割した最初の数字を足した数字を書いて隣のB教授に回す。5000+1000=6000だ。A教授はランダムの数字5000を覚えておく。
(4) ここで、まわってきた紙は、ほかの人には見せてはいけない。B教授はまわってきた紙の6000に自分の給料を分割した数字をひとつ選んで足し、さらに隣の人に回す。こうして足しながら3周まわす。
(5) A教授は、最後に紙が戻ってきたらそこから(3)のランダムな数字5000を引く。出来上がった数字が給料の平均値だ。
ここで、(3)でランダムな数字が登場するのは、B教授が、「A教授は最低でも1000*nドルの給料をもらっている」という情報を得ないようにするため。３周まわすようにしたのはなんとなく。２周でもいいような気がする。
人生は七転び八起き、一日は早寝早起き
Re:ランダムに分ける案 (スコア:1)
ん？
で、1周させる間、他の人に見せないというルールを使ってよいなら、こういう手がありますね。巡回の最初の教授をA教授、最後の教授をZ教授としましょう。
これで2周でどうにか。Z教授に対する信頼が必要になりますが。
ただ…この方法だと、「小さな紙」に書いてある数字を「消して、新しい数字を書き込む」必要がある。でも条件には「消しゴムの存在」は含まれていないんだよね…。塗りつぶす方法だと「小さな紙」ではすぐ空間が足りなくなると思うんだ…。
fjの教祖様
Re:ランダムに分ける案 (スコア:2)
やっぱり裏に書いたら駄目ですよねー
Re:ランダムに分ける案 (スコア:1)
あー、
「一周目は紙をもらったら計算結果を新しい紙に書いて、古い紙の結果は塗りつぶす」
「二周目は紙をもらったら計算結果を使い古しの紙の裏に書いて、もらった数字は塗りつぶす」
ならできるかも。
紙が１枚ではなく人数分だけある理由も立ちますね。
fjの教祖様
Re:ランダムに分ける案 (スコア:2)
確かにおっしゃるとおりな部分があります。私も仕事中に考えていて（ぇ）、紙に書く案はだめだなと思っていました。
最初にnで割る必要がないというのはごもっとも。最後に１回で十分ですね。
あと、ランダムな数字はA教授だけが考えておけば十分です。初期値を0にすると、B教授がA教授の給料の最低値を知ってしまうので、それをさせないための方便です。なお、ランダムの値を非負の値（≧０）としてしまうと、「A教授は最大で○○ドルもらっている可能性がある」とわかってしまうので負の値もありうることにしておかなければなりません。
でも、このランダムな数字というのはエレガントではないなと思い直しました。(2)で給料を分割するときに負の数に分けても良い（ex. 10000=-15000+5000）ことにすれば、B教授にはA教授の給料を推測できなくなるので、このランダム数字は不要になります。
紙に書いてまわすように考えていたのですが、こうするとご指摘のとおりで数字の履歴が丸見えになってしまいます。そこで、やや強引ですが、小さい紙は手順（２）で分割した数字をメモする紙ということにして、足し合わせた数字は耳打ちすることにしたほうが良いと考え直しました。
以下、直した手順。
(1) n人の教授がいるとする。
(2) 各自、(1)の値を２個に分割する。例えばA教授が10000ドルもらっているなら、10000=4000+6000など。負の数も許容する。この数字を小さい紙にメモする。
(3) みんなで輪になって、最初のA教授は最初の数字を隣のB教授に耳打ちする。
(4) B教授は自分のメモにある最初の数字をA教授から聞いた数字に足して、C教授に耳打ちする。
(4')C教授は自分のメモにある最初の数字をB教授から聞いた数字に足して、D教授に耳打ちする。以下繰り返す。
(5) A教授が、最後にZ教授から聞いた結果をnで割ると平均値が求まる。
人生は七転び八起き、一日は早寝早起き
Re:ランダムに分ける案 (スコア:1)
給料を2つ以上に分割する、と言う考えは tarosuke さんも提示していますが、それは単に
給料 = 乱数1 + (給料 - 乱数1)
に分割しているだけです(あ、上記は2つに分ける場合ね)。つまり、分割する段階で乱数が入り込んでいるので、数字を「なんと表現しているか」以外何も変わっていません。
fjの教祖様
少し修正が必要 (スコア:2)
okky氏の元の回答では、ランダムな数字について、個々の値が誰のものかは
分からなかったとしても、全ての値の集合としては分かってしまいます。
すると、各教授の申請した値から各教授の給与の取りうる値（特に上限と下限）が
分かってしまうので、このままだと題意に合わないのではないかと思います。
少し修正して次のようにすると概ね題意を満たすのではないかと思います。
ランダムな数字はランダムな結果としてであればたまたまごく小さい値（たとえば0）を
使うことになっても構わないと思います。他人に意図を読み取られない自信があれば
ランダムではなく恣意的な値をつかっても構いません。
あと、制約条件としてはokky氏の示したものに加えて、紙に書いた文字の筆跡で
誰が書いたか特定されないという条件が必要なのではないでしょうか。
筆跡でわかるなら。 (スコア:2)
極端に紙が小さいならば、鉛筆で字書けないよな。ましてや、1,000,000,000,000 みたいな桁が多い数字書けないよ。
ひとりが1桁で、もう一人が10桁、もう一人が100桁だったらどうするんだ。３人で計算する場合で、オレの給与は、1.00001 だ！みたいな奴がいたら更に面倒そうだ。3進数に変換することができれば、なんとかなりそうだが、"オイラだって給与に小数点が欲しい"みたいな主張はありそうだ。正式な給与は、100π万円だが、年末に小数点以下は円単位に切り上げる みたいな規則だったら、打つ手なしだ。そもそも給与は一定なんだろうか。
(1) 壁に鉛筆で線を引く。
(2)小さいが、有限の面積を持つ紙を必要そうな桁数分だけにさらに細かく破って、足りなければ誰かの髪を引き抜いて、桁数ぶんだけ確保。あるいは鉛筆を折る。
(3)給料+乱数ぶんだけ、上げたり下げたりする。
(4)それぞれの教授が、適当な順序で、桁ごとに上げたり下げたり疲れるまでつづける。上げたり下げたりのプロセスの間、操作を行っている人以外は後ろ向いている。
(5)各自が最後に乱数の部分を責任を持って正しく差し引く。
やっぱり物理的に桁数分だけのオブジェクトを用意するのがいやなら、1の桁から初めてもよさそう。終わることができないのが欠点だが。
.. ああ。今なんでそんなトラブルが発生したか、顧客に説明する資料作っているのさ。「各自が、責任もって正しく」「第３者レビューを行う」とか。
紙は一枚でいいんじゃね？ (スコア:1)
計算能力に問題がないとして。
適当な所から自分の給料以下の適当な数字を書いてスタート。
順番に一周させる。
次からは自分の給料から過去に書いた数字の合計を引いて、それ以下の適当な数字を書き加える。
全員の書ける数字がゼロになったら終了。
で、数字を全部合計して人数で割れば平均が出る。
# 途中の数字一つ一つはて意味を持たないのが鍵。
Re:紙は一枚でいいんじゃね？ (スコア:1)
それだと、誰がどの数字を書いたのかを覚えていれば、すべての人の給料が解ってしまいますが…
fjの教祖様
Re:紙は一枚でいいんじゃね？ (スコア:1)
隣の人にしか見せず、毎回逆向きに紙を回せばいいだろう。
Re:紙は一枚でいいんじゃね？ (スコア:1)
まず、逆向きに回すために方向を逆転させたポイントで情報が漏れる。つまり逆転させた次の教授は「逆転ポイントになった教授」が操作する前と操作した後の情報を手に入れられるので、むしろ情報が増えてしまう。回転方向は一定でなくてはいけません。
隣の人…もし「１つ前の人」に見せたら「自分が書いた値」と「変化した値」の差分から、『見せている人が追記した情報』が露呈するよね。
「次の人」だけに見せる…つまり「紙を手渡すまでは見せない」が「紙を手渡された人は紙に書かれている事は見える」という条件なら、「数字を全部合計して」という条件が成立しなくなるが?
fjの教祖様
Re:紙は一枚でいいんじゃね？ (スコア:1)
あ、もう一つ弱点があるわ、それ。
仮に各教授が「あまり記憶力が良くない」と仮定したとしても、うまくいかない。
という条件があるのだが、それだと各教授の言う数字の最大値を覚えておけば「少なくとも xxx は yyyyドル以上は稼いでいる」という情報が手に入ってしまう。
あまり大きな数字を言うと「xxx は vvvvv ドル以上稼いでいるのか」となるし、
あまり小さな数字を言い続けると、いつまでも数字を言い続けなくちゃいけないので「xxx は vvv ドルを w 回も言えるぐらいは貰っているのか = vvv * w 以上貰っているのか」が解ってしまう。
つまり、あまり給料に大きな開きがない、という大前提がないと、各教授が戦略を立てることすらできない。
fjの教祖様
Re:紙は一枚でいいんじゃね？ (スコア:1)
「その数字は十分に小さく、給料以下である事が自明」であれば情報ではないというのが「情報を得ていない」の根拠なのだが、そこまで疑うならマイナスを書くのもOKとすればいい。これで給料以上の数字も書ける。「逆向きに回す」と併せてね。
Re:紙は一枚でいいんじゃね？ (スコア:1)
それは最初に乱数を足した数字を述べて、その後乱数分だけ引き算する方法と言っている事は同じ。
分割する意味がまるっきりない。
fjの教祖様
巡回群でOK? (スコア:1)
教授は信用できないとは書いてないので、数学的には全員で十分大きな数を決めておき、乱数＋賃金を割った余りを常に用いることにすれば（巡回群で計算）完全正答な気がします。
周りが信用できなければ、準同型暗号使って電子投票することに・・・
#数学教授ならきっと暗算で復号してくれる！
Re:巡回群でOK? (スコア:1)
？？？
確かに「巡回群上での」平均値は求まるだろう。
しかし、最後に「本当の平均値」に戻す方はどうするんだ? 巡回群上の1つの値に対して、整数が n 個対応するからこそ、実際の値を隠せるわけだろう? 隠しきれるような値なら元に戻せないし、元に戻せるなら個々の数字ももとに戻せてしまうではないか(巡回群上をぐるぐる回っているのは乱数の部分だけであって、賃金の部分は実は一意決定だって事になるから、後で乱数の影響を取り除くために引き算をするときに、個々の賃金も露呈してしまう)。
おぉ。後は鉛筆と紙だけでどうやって 電子投票 するのかという問題をとけば…ってダメやんっっ!!暗号化・復号化処理を暗算でできるかどうか以前の問題やん。
数学教授に機械が組み立てられると思っているのか?!
(あれ？？それもなんか違う問題のような…)
fjの教祖様
Re:巡回群でOK? (スコア:1)
！？
巡回群で計算した合計＝元の数での合計、じゃだめでしょうか？ 有限桁の加減算で桁あふれ無視しても結果が表現範囲内ならOKというのと同じだと思うのですが。
乱数サイズは賃金の合計に比べて大きく取る必要があり、そのままでは最大の乱数を出した人が簡単に特定されてしまうので、巡回群にして乱数の一様性を保証する必要があると思います。
あと全く失念していましたが、乱数と加算後の値が近いことを利用して紙片の持ち主を特定という抜け道を潰すため、あらかじめ２グループ以上に分け紙片の集計は別グループに任せる、といった手順を踏む必要があると思われます。
#これだと4人以上になっちゃう？
すべった元の言い訳すると、「準同型暗号使った電子投票と同じ秘密計算」。
#眠気の中で書くもんじゃなかった・・・
Re:巡回群でOK? (スコア:1)
そのためには、「各教授の給料の最大値」が判らないと駄目では? そういう情報を取得できてはいけない、という拘束条件があるんですが。
Boldで強調した条件のせいで、巡回群の大きさを決められない、という拘束条件が出てしまうのですが…。
# つまり、こいつらの中には何兆ドルも稼いでいる奴がいるかもしれないってことで…
fjの教祖様
Re:巡回群でOK? (スコア:1)
「(集まった)各教授の給料」はともかく、「一般の給料」ならたとえば[0,ドルの発行残高)と言う風に決めてしまって構わないと思うのですが・・・
こういった解釈がだめだとすると、給料は（-∞,∞）である必要があり、紙に書こうが背中に指で書こうが声で伝えようが伝達時間から有限桁であることが分かってしまうので、そもそも情報のやり取りが一切禁止されるはずです。
Re:巡回群でOK? (スコア:1)
うーむ。その巡回群は結局「何を判らないように」しているのでしょう?
例えば巡回群を[0から10京)のように決めたとしましょう。
で、私の年俸と乱数を足したら 30万ドルで、乱数として(10京-20万)ドル足したとしましょう。
…年俸は巡回群を「巡回できない」ぐらい十分小さく、乱数は「巡回できる」ぐらい大きな値をとりうるんですよね? この条件だと…何を隠しているの?? 給料?? それとも乱数??
fjの教祖様
Re:巡回群でOK? (スコア:1)
あ、勘違いで混乱しつつ説明があほすぎて本当に申し訳ないです。
長いですが・・・
N+1人を一人P0と残りPn（n=1..N）に分かれる
・P0は白紙で紙をP1に渡す
・P1は適当な数C>>Max(Xn:Pnの給料)をもらった紙に書き、P0に見せないようにP2...PNに回す
・Pnは乱数An + 給料Xn mod C = Rnを書いてP0に渡す。An>>Cで、Anは口頭で開示する
・P0はX0+Sum_n(Rn)を口頭で報告する (Sumは1...n)
P0: X0, R1...RN, A1...AN
Pn: C, Xn, Rn, A1...AN, (sum_n(Rn) + X0)
An + Xn mod C = Rn
から、あるBnがあって
Xn = C * Bn + Rn - An
だが、P0はCがわからないのでBnとXnがわからない。
PnはCとAnがわかるが、RnがわからないのでXnとBnがわからない。
Sum_n(Rn) + X0 - Sum_n(An) mod C
= Sum_n(An + Xn - C * Bn - An) + X0 mod C
= Sum_n(Xn) + X0 mod C
= Sum_n(Xn) + X0
Avg = (Xp + Sum(Xn)) / 人数
Pn全員がわかったので答えをP0に教えて終わり。
mod Cを省略して、An+Xn=Rnとすると、P0にはAnとRnからXnがわかってしまいます。
最初の案のように、Rnをうまくシャッフルできればmod cなしでもいいのですが、ただ乱数を使っていると一番近いAnを使う、などといったトリックが使えるのであまり効果がありません。
#小さい部屋=紙片を使わず口頭で申告すると全員に聞こえてしまう、という制約がAnとRnだけではXnがわからない手段を必要としています。
たぶんこれで会ってるはずですが・・・まだ間違ってたらごめんなさい。
Re:巡回群でOK? (スコア:1)
C ≫ Xi が成り立つなら、「Pnは乱数An + 給料Xn mod C = An + Xn = Rn」になるじゃないですか。そしてそれを「全員が知っている」状態になります。
An と Rn から Xn が判らないようにするには「 C ≫ Xi が成り立たない」必要があるはずです。
fjの教祖様
Re:巡回群でOK? (スコア:1)
すみません「Piは乱数Ai>>Cと給料Xiから、Ri := (Ai + Xi) mod Cを計算し～」と読み替え願います。
Ai + Xi >> Cなので、ある自然数Biがあって、Ri := (Ai + Xi) mod C == (C * Bi + Ri) mod C != Ai + Xi
Riの計算や平均の計算をするのはmod Cで、Aiの通知は一般の数で行います。（Ai mod Cではなく）
会話は除数C（秘密鍵）で暗号化されているので、Cを知らないP0（Riの集計係）はAiが聞こえていてAiとRiが全て分かっているのに、Xi（とBi）は分かりません。
# mod が左側全体にかかるのって整数論あたりの方言なんでしょうか
# あとRとA逆にするべき鍵はKで添字はiだろとか。重ね重ね書き方悪くて申し訳ないです。
Re:巡回群でOK? (スコア:1)
「乱数 Ai に対して Ai ≫ C」というのは、すべからく「乱数 Vi を定義して C ＞ Vi ≡ Ai mod C」であるのと同じですよね？
なら、Ai の代わりに「C-Xi ＞ Vi ＞ -Xi であるような乱数 Vi だけを使う」としているのと変わらないじゃないですか。
一見巡回群のように見えるこの系は、CがXiに比べてあまりにも大きいと、実は「巡回群じゃない」と仮定して計算できてしまう、と言う事です。
fjの教祖様
Re:巡回群でOK? (スコア:1)
「乱数 Ai に対して Ai ≫ C」というのは、すべからく「乱数 Vi を定義して C ＞ Vi ≡ Ai mod C」であるのと同じですよね？
ViからAiをつくる、と言う意味なら、Ai mod C == ViとなるAiは無数にあるので違ってきます。
Ai の代わりに「C-Xi ＞ Vi ＞ -Xi であるような乱数 Vi だけを使う」としているのと変わらないじゃないですか。
「～」は、「Aiの範囲をC>Ai+Xi>0となるようにする（その後AをVに書き直す）」と等価ですが、そうするとBi = Ai + Xn div Cは常に0になります。
BiはP0(Rnの集計者)には分からない数値である必要があり、重要な点が変わってしまっています。(Ai >> Cはそのため)
CがXiに比べてあまりにも大きいと、実は「巡回群じゃない」と仮定して計算できてしまう
のではなく、「Bi=Vi + Xi div Cがゼロであるとき、～計算できてしまう」のであって、CがXiに比べて大きくてもAiがCより十分に大きくBiが推定できないなら、RiとAiからXiを計算できません。
求めることは出来ないとして考えてみる (スコア:1)
他の方のコメントにもあるような、自分以外の教授が書いたメモの内容（たとえ適当な数字の羅列だとしても）を
得ることが出来ないのであれば、平均を求めることは出来ない。って解はダメ？
Re:求めることは出来ないとして考えてみる (スコア:1)
…なるほど。
ので、無理…おぉ、その解はありかもしれない。
fjの教祖様
もう一つずるい手を考えてみた (スコア:1)
解放された後に、一緒に閉じ込められていた教授達全員で、
給料を管理している部署にいってメモを渡し、
メモを渡した教授の平均給料を教えてくれと聞いてみる。
給料の支払元が違ったりすると成立しないけど。
Re:求めることは出来ないとして考えてみる (スコア:1)
「求めることはできない」が正解かもしれない、と考えていたら気づいたのですが。
「(平均*人数)ドル以上稼いでいる教授はいない」という事実は得てはいけないので、
・平均を得ることはできない
・負の給与を得ている者がいる
・部屋には教授達が何人いるか分からない
のうち、少なくとも1つは成り立っているはずです。
負の給与はないとして。
平均を得ることができるならば「人数が分からない状態」をどのように作り出すかが重要かもしれません。
# 「情報は何も得ずに」は無理、が答えとしては何ら不備がないエレガントな回答な気がしますが……
1を聞いて0を知れ!
Re:求めることは出来ないとして考えてみる (スコア:1)
きっと「11人いる」状態なのですよ。
# 数学教授が10人しかいないはずなのは知識として判っている。
# しかし、誰が残りの10人を見ても、全員数学教授だ、と認識してしまうように暗示をかけられている。
面白い前提ですが、「給与の平均値」と「人数」から演繹される全ての情報は「シャノンの定義」に従えば、情報量0です。
なので「給与の平均値」や「人数」から割り出せる、他の情報を取得するのは構わないのでしょう。
まぁ、アリシア人やエッドール人が相手の場合は、それだけの情報があればその情報が存在する宇宙全域について知ることが可能なのでしょうが…
fjの教祖様
Re:求めることは出来ないとして考えてみる (スコア:2)
給料ではなく、予算と従事者数等の情報を書いてもらうのは厳しいですよねぇ・・・
＃予算はわからんけど、ある程度雑談で取得出来そうｗ
ランダムな数字って、ひとつじゃダメですか？ (スコア: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の教祖様