慶應・環境情報学部の情報科目2017年度の「6次の隔たり」問題を解ける方いませんか？

Question

慶應・環境情報学部の情報科目2017年度の「6次の隔たり」問題を解ける方いませんか？
来年、慶應を受ける浪人生です。
去年この問題がまったくわかりませんでした。

問題（24P～27P）→https://goo.gl/oBbrhH

自分なりにといてよくわからない所をまとめました。

---

①すべてのx∉Gに対して友人の集合F(x)と書いていますが、図のようにxの友人のことをF(x)というという解釈で間違いないでしょうか？

②これはxの友達にyがいた場合のことを言っているのでしょうか？

③図にの解釈で間違いないでしょうか？

④なぜxとyの距離が（xとyの要素数）- 1 なのでしょうか？
これは距離にyを含んでいるから-1なのでしょうか？

⑤これはまったく言いたいことがわかりません。一応自分の解釈を図にしました。

---

---

自分でわかるとこだけ解いていますが、たぶんあっていないところもあると思います。
番号のところは分からないところです。

よろしくお願いいたします。

Comments

[yuba]

どの空欄がわからないのですか？ 例えば最初の空欄に入るのがGであることは考えるまでもなく明らかです。

Answer 1

空欄を埋めてほしいとは書いてませんでしたので、とりあえず質問についてだけ回答します。

①すべてのx∉Gに対して友人の集合F(x)と書いていますが、図のようにxの友人のことをF(x)というという解釈で間違いないでしょうか？

そうです。

②これはxの友達にyがいた場合のことを言っているのでしょうか？

"y ∈ F(x)" は、「x の友達のうちの一人を y とする」という意味です。
「y がいた場合」という言い方はちょっとおかしいです。

③図にの解釈で間違いないでしょうか？

y につながっているのは z_3 ではなく z_n ですが、それ以外は合ってます。

④なぜxとyの距離が（xとyの要素数）- 1 なのでしょうか？
これは距離にyを含んでいるから-1なのでしょうか？

そうだと考えてもらって構いません。
要素数が1のとき ⇔ x=y のとき、距離を 0 にしたいからです。

⑤これはまったく言いたいことがわかりません。一応自分の解釈を図にしました。

ご記載の図の解釈はあまり正しくありません。
2. は、s から一番遠い友達の集合を求め、その中から t を一人任意に選ぶという意味です。
3. は、t から一番遠い友達の集合を求め、その中から u を一人任意に選ぶという意味です。

---

空欄も埋めてほしいということでしたら、後で回答します。

Comments

[codetaisei]

回答ありがとうございます。

⑤に関して理解が追い付きません。
なぜs から一番遠い友達の集合を求め、その中から t を一人任意に選び、
そのｔから一番遠い友達の集合を求め、その中から u を一人任意に選ぶ必要があるのですか？

＞＞空欄も埋めてほしいということでしたら、後で回答します。
質問後に回答を見つけたので答えは知っています。

[yuki23]

その説明が書いてあるのがp26からの（イ）です。それは解きましたか？

[codetaisei]

（条件γ）あるv,wについてd(v,w)＞d(t,u)と仮定し、矛盾を示す。
もしd(v,w')＞d(v,w)となるw'があれば、w'を改めてwとおくことができるので、
すべてのx∈Gに対してd(v,w)≧d(v,x)としてよい。

まず、P(s,t)とP(v,w)に共通部分があることを示す。
sとwの経路が存在するので、それがsとtの経路と分岐する箇所をa,
vとwの経路と分岐する箇所をbとする。
（条件αより）

d(s,t) = d(s,a) + d(a,t) ≧ d(s,w) = d(a,s) + d(a,b) + d(b,w)

となる。同様に
（条件γより）

d(v,w) = d(v,b) + d(b,w) ≧ d(t,v) = d(b,v) + d(a,b) + d(a,t)

となる。この２つの式の不等式の両辺を足して整理すると0≧d(a,b)となるが、距離は負にならないのでd(a,b)=0となり、P(s,t)とp(v,w)には共通部分が存在することがわかる。

c∈P(s,t)∩P(v,w)とする。cはP(s,v)P(s,w)のどちらかに含まれるが、P(s,v)に含まれる場合はvとwを交換して考えることができるので、c∈P(s,w)としてよい。
（条件αより）

d(s,t) = d(s,c) + d(c,t) ≧ d(s,w) = d(s,c) + d(c,w)

であるからd(c,t)≧d(c,w)となる。同様に
（条件γより）

d(v,w) = d(v,c) + d(c,w) ≧ d(t,v) = d(v,c) + d(c,t)

であるからd(c,w)≧d(c,t)となる。この2つの式からd(c,t)=d(c,w)となる。
（条件βより）

d(t,u) ≧ d(t,v) = d(v,c) + d(c,t) = d(v,c) + d(c,w) = d(v,w)

となる。これは最初の仮定に反するので、証明された。

[codetaisei]

回答を見てまとめましたが、さっぱり理解できません。

Answer 2

###⑤に関して
これを可能にしているのは、データの性質として3つ目に挙げられている「x,yの経路がただ1つ」と言うものです。これは言い換えれば、知り合いの知り合いの…と繋ぐ線が1本であり、A↔B↔C↔Aのようにループする場所が無いということです(このようなループがある場合、AとBの経路が{A,B}と{A,C,B}のように複数存在することになる)。
これを踏まえると、集合Gを友人の網と考えると、ループがないため必ず端となる人物が存在します。
直感的に考えると、最長候補はこの端から端までの長さということになります。それを調べるため、まず適当なところから一番遠い端を探し、その端から最も遠い端を探して最長としていることになります。
詳しい証明はこの問題でやっていることでしょう。

で、この証明ですが、まずsとtの経路とvとwの経路に共通部分があることを示すために、次の図のように点を設置しました(便宜上、人物に相当するものを点と呼びます)。

これで、sからwまで、s→a→b→wとたどればいけます。
ただし、条件αから、st間はsからどこへ行くよりも遠いか同じなので、d(s,t)≧d(s,w)です。
これを各点までの長さに分割した式が(102)より、からの式です。
同じことをvw間とvt間でもやります。
その結果、ab間の距離が0以下という結論に至りましたが、距離は負になりませんので、ab間は0です。
これは、aとbが同じ点であることを意味します。つまりこうなります。

これで2つの経路に少なくとも1点共通部分があることが確定しました。

次に、こんな風に点cを設定します。

前段と同じように、st間がsからの経路中最長であることを利用し、cからの距離比較を行います。vw間も同じです。
計算を進めると、ct間はcw間以上かつ以下、ということになったので、これを満たす関係は「ct間とcw間は等しい」しかありません。
そして、条件βからtu間はt起点経路中最長なので、tv間はそれ以下ということになりますが、先ほど示した「ct間とcw間は等しい」から、tv間はvw間と等しくなってしまい、「vw間はtu間以下」という帰結になります。しかしこれは最初の仮定の真逆です。つまり最初の仮定がおかしいということになり、tu間が全経路中最長ということになるのです。

Comments

[codetaisei]

回答ありがとうございます。
すごくわかりやくて助かりました。

質問があるのですが、
①この問題は慶應の環境情報学部の情報科目の2017年の問題なのですが、これって普通の高校生が解ける問題なのでしょうか？
②このような数学とアルゴリズムを利用した穴埋め問題はどうすれば解けるようになりますか？
一応、基本情報技術者の午後試験でアルゴリズムを勉強していますが、それだけでこのような問題を試験会場で導き出せるのでしょか。