次の問題がわかりません・・・。
皆さん教えてください↓
第一問 一辺が1の立方体ABCD-EFGHを、対角線AGを含む平面で切断するとき、
切り口の面積の最小値を求めよ。
第二問 n個の空港の間に以下の(・),(・)の条件を満たすような直行便を開設するとする。
(n≧3とする)
(・) どの相違なる二つの空港A,Bの間にも、AからBへの、あるいはBからAへの直行便のどちらか一方を開設する。
(・) ある空港Cから出発し、直行便を乗り継いで、またCに戻ってこられるような空港Cが少なくとも1つは存在する。
このように開設する方法がan通りあるとする。
(1)a3を求めよ
(2)a4を求めよ
(3)anを求めよ
よろしくお願いします。
No.2ベストアンサー
- 回答日時:
第一問
こちらは簡単なので端折らせてください。
辺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
- 回答日時:
第二問ですけど、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
- 回答日時:
1の方は出来たけど
納得してもらえるかどうか分からないので
もう少し議論を詰めてから。
んで2の方ですが、
例えば経路の例として
A→B→Cと
A→C→Bは
違うものとして捉えるんですか?
それとも同じものですか?
もしそうであれば、この問題は
ある多角形にどれだけ対角線を引く方法があるか
という問題に還元できますけど。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
成田空港から日本武道館に行く...
-
フランクフルト空港または中央...
-
飛行機の運行状況(韓国→福岡)
-
税関の営業時間ってどうなんで...
-
羽田空港ターミナル2のラテン語
-
transitとtransferの使い分けに...
-
プライベートジェットってどこ...
-
空港 売店バイト
-
食物検疫
-
成田空港第1PTBとは?
-
★セントレア付近格安駐車場★
-
羽田空港への行き方
-
タクシーで東京駅から水天宮ま...
-
オークランド国際空港での乗り...
-
高松空港から坂出へ行くには
-
福岡空港で写真のフィルムが買...
-
デルタ航空サポートセンターの...
-
オレンジ色の服・・・?
-
メルボルン空港に早朝着きます...
-
チャイルドシートの梱包(航空...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
福岡空港で写真のフィルムが買...
-
成田空港から日本武道館に行く...
-
一目ぼれした人ともう一度会いたい
-
成田空港第1PTBとは?
-
空港 売店バイト
-
高速のサービスエリア,空港のお...
-
空港の金属探知機に体内に埋め...
-
変電機は空港やホテルで売って...
-
アンケート調査についてです。
-
ロサンゼルス空港
-
福岡空港国内線の待ち合わせ場所
-
搭乗者名を調べることは可能で...
-
飛行機の運行状況(韓国→福岡)
-
成田空港第1ターミナルでの待...
-
羽田空港ターミナル2のラテン語
-
新千歳空港の飲食店や売店は朝...
-
世界最大の空港は?
-
ロンドン・ヒースロー空港での...
-
ハンディーターミナルのレスポ...
-
表参道は本当に滑走路だった?
おすすめ情報