教えてください

質問

次の問題がわかりません・・・。
皆さん教えてください↓
第一問 一辺が１の立方体ABCD-EFGHを、対角線AGを含む平面で切断するとき、
切り口の面積の最小値を求めよ。

第二問　ｎ個の空港の間に以下の(・),(・)の条件を満たすような直行便を開設するとする。
（ｎ≧３とする）
(・) どの相違なる二つの空港A,Bの間にも、AからBへの、あるいはBからAへの直行便のどちらか一方を開設する。
(・) ある空港Cから出発し、直行便を乗り継いで、またCに戻ってこられるような空港Cが少なくとも1つは存在する。
このように開設する方法がaｎ通りあるとする。
(1)a3を求めよ
(2)a4を求めよ
(3)anを求めよ
よろしくお願いします。

回答No.2

Umada · ベストアンサー

第一問
こちらは簡単なので端折らせてください。
辺BC上に新たに点Pを取ります。
平面APGで立方体を切断するとして、三角形APGの面積を考えます。
線分AGを底辺に取り、直線AGとPとの距離を高さに見ることができます。AGは(√3)aで一定ですから、問題は直線AGとPとの距離の最小を求める問題に帰着します。
やり方はいろいろあると思います。点と直線の距離の公式を使っても良いですし、ベクトルで解く方法もあるでしょう。(結局、PがBCの中点に来た時に面積最小になるはずです)

第二問
これは難問でした。
(1)3つの空港の場合。3つの空港のうち、2つを結ぶ線(向きは問わない)は3つあります。
それぞれについて「A→Bだけ開設する」「B→Aだけ開設する」の2通りがあります。
従って条件がこれだけなら、2^3=8通りの路線網が作れます。

そのうち、元に戻れる空港が存在するのは空港をA, B , Cとして
A→B→C→A
A←B←C←A
の2通りのみです。a3=2です。

(2)4つの空港の場合
(イ)元に戻れる空港が存在するn=3の路線網に4つ目の空港Dを加える場合
4つ目の空港Dと、それ以外の3個所の空港の間の路線3本はどの向きの路線を開設しても題意を満たします。
このような路線網は　a3×2^3　通りできます。

(ロ)元に戻れる空港が存在しないn=3の路線網に4つ目の空港Dを加える場合
以下の補題に従えば、そのn=3の路線網には「到着便しかない空港」が1つだけ存在します。この空港をXとします。
(ロ-1)XからDへ向かう便を開設し、残りの2つの空港との便のうち少なくとも1つはDからの出発便にする。
元に戻れる空港がないn=3路線網は　(2^3-a3)通り=6通り
XからDへ出発便を開設する方法は　×1通り
残りの2空港への便開設法は　×3通り　(=2^(n-2)-1)
従って　3(2^3-a3)=18通り。
(ロ-2)X空港へはDから出発便を開設する。(従ってXは到着便ばかりのままであり、残りの3空港の間で巡回可能にしなくてはならない)
残りの2つの空港とD空港との間で回ることができるようにする。
X空港の選び方で　3通り　(=(n-1)通り)
残りの(n-1)空港＝3空港の間で回れる路線開設法は　×2通り(=a3通り)
従ってこのような路線開設法は　6通り。

(イ)(ロ)を足して　40通り。

(3)
n個所の空港間に路線網を開設する方法は　2^(n(n-1)/2)　通り。以下では補集合で考えます。

元に戻れる経路が一つも存在しない場合、到着便のみの空港が一つだけ存在します。
n個所の空港のうち1個所を選びXとします。X空港は到着便のみとします。残りの(n-1)個所の空港で巡回できるかできないか考えますとそ、それぞれにつき
(n-1)個所で巡回経路がある路線網　a[n-1]通り
(n-1)個所で巡回経路がない路線網　2^(n-1)(n-2)-a[n-1]通り
が存在することが分かります。Xの選び方でn通りありますから、n個所の空港を結ぶ路線網で巡回経路がある路線網の数は、全体から巡回経路がない路線網の数を引けば良いわけですから
an=2^(n(n-1)/2)-n×{2^{(n-1)(n-2)/2}-a[n-1]}
という漸化式が成り立ちます。

ここでan＝bn×2^{n(n-1)/2}なる新しい数列bnを考えると
bn×2^{n(n-1)/2}=2^(n(n-1)/2)-n(2^{(n-1)(n-2)/2}-b[n-1]×2^{(n-1)(n-2)/2})
ですので
bn×2^(n-1)=2^(n-1)+n×b[n-1]-n
となって
(bn-1)×2^(n-1)=n(b[n-1]-1)
よって、
bn-1={2^(1-n)×n}×(b[n-1]-1)=(2^{(1-n)+(2-n)}×n(n-1))×(b[n-2]-1)=.....
と順に式変形して
bn-1=(n!/3!)×2^{-(n-3)(n+2)/2}(b3-1)
b3=1/4ですから
bn=-(n!/6)×2^{-(n-3)(n+2)/2}(3/4)+1
　=-n!×2^(-n(n-1)/2)+1
と求められます。anに直して
an=-n!+2^{n(n-1)/2}
でどうでしょうか。
検算をしますと
・a3, a4とはとりあえず合っている
・nを無限大に近付けると、an/2^{n(n-1)/2}は1に近付く(巡回経路のない路線網の割合は小さくなる)
ですので、よさそうです。

答えは実にスッキリしているのですが、少々複雑な計算だったので間違えているかも知れません。「自信なし」にさせてください。

--------
補題1
仮定：どの空港にも少なくとも一つ出発便があり、かつ、他の空港を経由して戻って来られる空港が一つもないとする。
空港イの出発便の一つを任意に選び、その到着地ロについて考える。ロにも出発便があるから第三の空港ハに向かうことができる。ハからも同様にどこかの空港へ向かうことができる。
しかし空港の数は有限であるからこの過程を繰り返せばいつか、到着したことのある空港のどれか一つに戻ることになる。矛盾。
結論：他の空港を経由して戻って来られる空港が一つもないとするならば、到着便しかない空港が少なくとも一つ存在する。

補題2
到着便しかない空港が存在する場合、それはただ1つだけ存在する。もしそのような空港が2つ存在するなら、それらの空港の間を結ぶ便は両方が到着地ということになり矛盾する。
--------