教えてください

質問

次の問題がわかりません・・・。
皆さん教えてください↓
第一問 一辺が１の立方体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つ存在するなら、それらの空港の間を結ぶ便は両方が到着地ということになり矛盾する。
--------

回答No.3

stomachman

第二問ですけど、Umadaさんと答は一致しました。しかしアプローチはいささか違うと思うので、ご参考までに。

　空港を頂点とし、直行便を辺とするグラフ（辺が向きを持つ有向グラフ）を作ると考えます。n個の空港のどの2つを取っても直行便があるんですから、もし辺の向きを無視すれば、これはただ一つ「完全グラフ」（どの頂点の間にも辺がある無向グラフ）しかありえません。すると問題は「少なくとも一つループができるように、完全グラフの辺に向きを付ける方法は何通りあるか」と言い換えられます。完全グラフの各辺に向きを与える方法は、辺の数をEとすると2^E通りあり、そしてE=n(n-1)/2ですね。だから「ループがないように辺に向きを付ける方法が何通りあるか」が分かれば、その数を2^Eから差し引けば良い。

　ループがないって事は、頂点間に順序が定義できるということに他なりません。「頂点xからyへの経路がある」という事をx<yと表したとき、どの頂点間でも直行便があるので、<は全順序になっていなくてはならない。
きちんと言えば、空港の集合をAとするとき、関係<が存在して
∀i∈A(￢(i<i))
∀i,j∈A( i≠j → i<j ∨ j< i)　（全順序である）
∀i,j∈A( i<j → ￢(j< i))　　　（ループがない）
∀i,j,k∈A( i<j∧j<k → i< k)　（推移則）
を満たす、ということですが （￢はnot、つまり否定を表す論理演算子です）ま、細かいことは重要じゃない。

ループがないのなら、この全順序<を使って頂点を一列に並べることができます。
a[1]<a[2]<.....<a[n]
また、このような列が一つ与えられると、「p<q なら pからqへの直行便がある」と解釈すれば有向グラフが丁度一つ作れます。かくて、このような列の数だけ「ループができないように辺に向きを付ける方法」がある訳です。もちろん、その数は頂点を一列に並べる順列の個数と等しく、すなわちn!通りあります。

以上から、「少なくとも一つループができるように辺に向きを付ける方法」は
2^(n(n-1)/2) - n!
通りあるということです。
n=3 では 2通り、 n=4では40通り。

回答No.1

NobNOVA

1の方は出来たけど
納得してもらえるかどうか分からないので
もう少し議論を詰めてから。

んで2の方ですが、
例えば経路の例として
A→B→Cと
A→C→Bは
違うものとして捉えるんですか？
それとも同じものですか？
もしそうであれば、この問題は
ある多角形にどれだけ対角線を引く方法があるか
という問題に還元できますけど。