平成１１年７月２６日
[流れ星]
第２４回数学的な応募問題
＜解答募集期間：７月２６日〜８月７日＞
［緊急連絡網］
問題です
＜浜田 明巳＞さんからの解答８月６日受信
第２４回数学的な応募問題について
Ｓ(ｎ)≦２ｎ−４を証明することになっているのですが，常識的な緊急連絡網では，無理なことだと思います．
通常の緊急連絡網は，発信源（担任）は１人で，最後に発信源が全員に行き渡った事を確認して終わります．
「災害時」のときに使う，ということですが，結局何が「災害時」か，です．阪神大震災規模の災害で有れば一目瞭然ですが，
大雨洪水警報くらいの状態では，はたして「災害」と言えるでしょうか．この判断は，やはり発信源（担任）でないと無理でしょう．発信源は１人でないと，混乱してしまいます．
Weekend Mathematics では，Ｓ(４)＝４の例として，
１→２，３→４，２→４，４→１
となっていましたが，この場合発信源が１，３となっています．仮に１が大本の発信源とすると，３がどうやって緊急連絡を始めるのが分かったのか．
ここでは，Ｓ(ｎ)≦２ｎ−３とするのが，妥当ではないでしょうか．この場合，
１→２，２→３，３→４，・・・，ｎ−１→ｎ，ｎ→１，１→２，２→３，３→４，・・・，ｎ−３→ｎ−２
の(２ｎ−３)回になります．
＜水の流れ：コメント＞ ８月７日
勿論、通常の我々の作っている緊急連絡網ではありません。
作問している時点では、阪神大震災規模の災害を想定しました。
当然、災害の時に、必然的に、発信源を連絡網のように決めておきます。そうすると、１回少なくて済みます。
安全確認の発信源は誰からスタートしても良いと思って作りましたが。
そして、連絡方法は最少であるものとしてあります。
先生のご指摘のような懸念はありますが、以上のように考えて作りました。
令和6年6月１3日 「二度漬け白菜」からの応募解答です
実際には S(n)=(2*n-4) であることが知られています．
S(n)≦(2*n-4)であることは次のように示せます．
(証明)
n人のうちの特定の4人を A,B,C,D とし，それ以外の(n-4)人を，
P[1],P[2],…,P[n-4] とする．
AとP[1]の二人が通話することを (A-P[1]) というように書き表すことにする．
n人のそれぞれが持つ独自の情報を，n人すべてで共有するためには，以下に示す
ように高々(2*n-4)回の通話で十分である．
(A-P[1])
(A-P[2])
(A-P[3])
……
(A-P[n-4])
(A-B)
(C-D)
(B-C)
(A-D)
(A-P[1])
(A-P[2])
(A-P[3])
……
(A-P[n-4])
つまり，まずAがP[1],P[2],…,P[n-4]と通話し，その後，A,B,C,Dの4人の間で
通話を行う．さらにその後，Aが再びP[1],P[2],…,P[n-4]と通話する．
これにより，S(n)≦(2*n-4) が示せた．(証明終)
