情報共有と電話の回数
私「N人の人がいて、その人たちはみんなすでに秘密を共有しているとする。そこにもう1人の人がやってきたとする」
長男「なるほど。その人のことを知るのにN回電話が必要なんだね」
私「その通り。情報がどこかでまとまるとしても、N人の人は少なくとも電話を1回取らなければ、新しい人の情報は得られない。これで必要条件のほうもいえる」
（ここで、電話がかかってきて、長男は遊びに行ってしまった）
N人の人がそれぞれ持っている情報を、電話を使って全員が共有するために必要十分な電話の回数は、
回。証明は数学的帰納法。
http://www.hyuki.com/diary/200501#i20050110
N人の人がいて、まだ完全に秘密を共有していないときにもう一人の人がやってきた場合も考えないと証明にならないよな…と考えていたのだが、反例があった。
AC, BC, CD, CA, CB と 5 回電話をかけると、ABCDの四人の秘密(遊べる時間)が共有できる。
私「A, B, Cの3人がいて、AとBが打ち合わせして、AとCが打ち合わせをして、Aがその打ち合わせの結果をBに戻す…そうか、3回で済むね」
と同じパターンだ。3人の場合はAB, BC, CAでもいいけれど。
2n - 3回 以下ではあるが、何回なのだろう、どう証明すればいいだろう？
- n 人がそれぞれ秘密を持っていて、みんなが自分以外の(n - 1)人の秘密を知るために電話をする回数は？
Aが二つ電話を持っている場合、Aが二つの電話で同時にBCにかければ計2回ですむぞ。
- n 人がそれぞれ秘密を持っていて、みんなが自分以外の(n - 1)人の秘密を知るために電話をする回数は？ただし、各人p_j個の電話を持っている。
追記(2005-01-10)
- 結城さんの日記が加筆された。私以外の読者さんにも必要条件がわかった方はいないようだ。グラフ理論の専門家キボンヌ。
- 結城さんの日記が加筆された。最初に全員の情報を得る人は二人だけで、それまでとそのあとの電話の回数の和で下から抑えられるわけか。「最初に」というのが難しい。
…ってやはり同時に全情報をえる人は複数存在しえるのでは。12人で20回ですむと思うのだが。
そもそも4人で4回でいいようなきがしてきた。AB,CD,AC,BD。寝ぼけてるのかな？寝ます。
追記(2005-01-11)
- 12人を思いついた後4人をすぐに思いつかずに結城さんの日記にfeedbackしてしまったのは、眠かったからだことにしよう…
- 電話での時間の摺り合わせのアナロジーに引っ張られすぎた。現実世界では共通の優先順位決定方法によるのでなく、頂点の独断で決まることが多い。
- 縦割り組織は効率が悪いということか。
