情報共有と電話の回数 - ヒビノキロク

http://www.hyuki.com/diary/200501#i20050110133233

ちょっと考えてみたけど、やっぱり(2N-3)回は必要だと思う。そのときの考え方を一言でいうとトーナメント戦。Nチームのトーナメント戦を考えると総試合数はK=N-1*1で、その時点で最初に全員の情報を知る組(優勝、準優勝)ができる。あとは同じことを逆向きに行なって、結局全体で2K-1=2N-3回の電話で全員が全員の情報を共有できる。

*1: $\small N=2^L$ のとき $\small K=1+2+4+\cdots+2^{(L-1)}=2^L-1$ 。 $\small M=2^L \ge N$ とすると、シード数が $\small M-N$ だから $\small K=2^L-1-(M-N)=N-1$