クイズ大陸クイズ大陸

参加型ナゾトキサイト『クイズ大陸』で、脳トレをどうぞ!

FAQ
feedRSS


このスレッドはロックされています。記事の閲覧のみとなります。
画像パズルトップ > 記事閲覧
不可能な配線?
日時: 2007/08/12 00:43
名前: Submarin

随分昔から頭を悩ませている問題です。

家が三件建ちました。ちょうど図のような状態です。
この家に水道、下水、ガスを配管することになったのですが、
地盤の関係で全ての配管が同じ深さにしか設置できません。
つまり管同士が交差できないのです。
三つの丸が元管です。ここから管を引いて三つの家をつないでください。
全ての家が三つの元管と繋がっていないといけません。
(つまり各元管から3本ずつ、全部で9本線を引く)
繋がっているなら曲線でも可能です。
但し、家同士をつなぐ配管して元管と接続したことにするのは不可とします。
(家と元管は、どこの家も元管も経由せず直接つないでください)

この問題は自力でやった限り、8本までは何とか引けるのですが、
9本目がどうしても引けません。
この問題はそれなりに知られているようなのですが、答えを掲載しているところがなく、
この問題自体に名前がないので答えの調べようもありません。
それ以前に、そもそも不可能ならその証明がほしいところのなのですが…
聡明な皆様方に質問させていただく次第です。

どなたか、9本の線を交差なく引けますか?
メンテ

Page: 1 |

Re: 不可能な配線? ( No.1 )
日時: 2007/08/14 23:59
名前: zen

家の上に管は通しても良いのでしょうか
良いのだったらできるのですが・・・。
メンテ
Re: 不可能な配線? ( No.2 )
日時: 2007/08/15 08:49
名前: 明日に

無理
メンテ
Re: 不可能な配線? ( No.3 )
日時: 2007/08/15 09:08
名前: ponta

zenさんへ OKです。

Submarinさん
確かに9本目が難しいっすね〜
でも、ちゃんとつながってる回答を見た記憶があります!!
ので、頑張ってやってみます。
3年くらいかかるかも。
メンテ
Re: 不可能な配線? ( No.4 )
日時: 2007/08/16 21:58
名前: Submarin

zenさんへ

図で見て、家の上側を通るということでしょうか?
それなら可能です。
メンテ
Re: 不可能な配線? ( No.5 )
日時: 2007/08/17 21:13
名前: 卵王子

家の上というのは、図の家に配管が重なるという意味では・・・?

「管同士は交差してはいけない」とは書かれてるけど
「管と家が交差してはいけない」とは書かれてません。

zenさんの指摘がOKなら確かに全ての配管が可能ですね。

なんか或いはそれに気付けるかどうかを試しているクイズのような気もしますね〜。
私もこのスレがたった日からずっと試行錯誤してるんですけど、
家に交差させない方法で可能になる方法が未だにみつかりませんし。
メンテ
Re: 不可能な配線? ( No.6 )
日時: 2007/08/17 22:48
名前: Submarin

図の家に配管が重なるというのは「家同士をつなぐ配管して元管と接続したことにするのは不可」に抵触します。つまり「元管→家→家」というふうになるのも、「元管→元管→家」となるのも、不可能配線です。
実際こんな状況になったら、使われる手段ではあるそうなのですが。
メンテ
Re: 不可能な配線? ( No.7 )
日時: 2007/08/18 22:16
名前: 卵王子

おっと、失礼しました、そういう記述があるのを忘れてました。
配管が通る深さを家より下と考えれば・・・とかまだ言い訳は立ちそうですが、
あくまで図面上で家と重なってはいけないということですね。
ん〜、やはり全然思いつきませんね〜
メンテ
Re: 不可能な配線? ( No.8 )
日時: 2007/08/18 23:05
名前: SAN

私も随分昔(?)に、友人から「同じような問題」を出されたことがあります。
でも、それはこちらの問題とは条件が少し違いますので、参考になるかどうかは…?
(家の数、元管の数など同じです。線が交わらないという条件も同じですが…)

「これ、できないだろ?」と私が答えると、その友人は楽しそうに(まるで「ひっかかったネ」というような顔で)「こうすれば…」と正解を描き示しました。それは、家同士をつなぐ配管で元管と接続する方法を使ったものでした。(下水は元管から直接3つの家に。水道とガスはそれぞれ左右から3つの家を通って…)その問題では「家同士をつなぐ配管…は不可」という条件がなかったのです。

確かに、彼は出題時にそれを「不可」とは言ってませんでした。でも、彼が私に問題の意味を図にかいて説明したとき、家同士をつなぐことをせずに8本かいて見せたので、私が勝手に「不可」だと思いこんだ(ひっかかった)のでした。

さて、実はこちらの問題。「…不可能ならその証明がほしいところ…」という言葉を見て、レスするかどうか迷ってましたが…
「家」や「元管」を「大きさのない点」として考えると…この問題は「できない」というのが答だと思います。

証明どころか説明にもならないと思いますが、その「つながり方」だけを考えると…
2つの家と2つの元管の「4点」をつなぐ場合、「家→元管→家→元管→(もとに戻る)」という「1つの閉曲線」になります。
ここに家を1つ増やすには、この「閉曲線」の内か外のどちらか。でも、いずれにせよ、それを2つの元管とつなげば全体の「つながり方」は同じ…。(スミマセン。私には、掲示板に図をかく技がないのです…)
そしてさらに、元管を1つ増やすには…と考えると、第3の元管をどこに置いても…???

「私はこう考えましたが…?」というだけの話です。表現の曖昧な点などあればどうぞ…と言いたいところですが、位相幾何など得意な皆様が私のこれを見たら「苦笑い」でしょうか…?
メンテ
Re: 不可能な配線? ( No.9 )
日時: 2007/08/23 21:11
名前: ミスターX

簡単でした。5分もかからずにできました。
メンテ
Re: 不可能な配線? ( No.10 )
日時: 2007/08/23 21:38
名前: 卵王子

ミスターXさんすごいですねーっ
どのように繋げたんですか?
メンテ
Re: 不可能な配線? ( No.11 )
日時: 2007/08/24 03:42
名前: Submarin

ここの掲示板、答えの絵が出来ても載せられないんですよね。
気になります。新スレッド立てて載せていただくというのは可能なんでしょうか?
メンテ
SAN氏に同意 ( No.12 )
日時: 2007/08/26 00:13
名前: ぽー

平面上で素直に考えたら不可では?
紙を一部折り返したり、家/配管に穴を開けて裏面に繋ぐかな?
メンテ
Re: 不可能な配線? ( No.13 )
日時: 2007/08/27 17:10
名前: REE

配管を家の地下を通してよければ出来そう。
(家同士を繋ぐのではなく、地下を貫通するだけ)

やはり、ここは、一軒をオール電化にしてもらうということで
メンテ
Re: 不可能な配線? ( No.14 )
日時: 2007/08/27 19:41
名前: Submarin

ぽー さんへ
一応答えは載っていないにしろ、ここにも「できた」という方がいますからね…
自分で解いていた間は「不可」論に傾きつつあったのですが、
気になってまた調べてみたところ、某所ブログにこの問題が出され、
(Googleで「パズル 線同士 交差しない」と検索すれば分かると思います。)
コメントバックに「解けた」との発言がありました。
(ここに掲載しているのと条件は全く同じ)
しかし、そこにも答えの図は載っていない!!
・・・誰か助けてください

REE さんへ
家や元管を『経由する』とダメなので「配管を家の地下を通して」というのはダメです。

あと、オール電化とはおもしろい発言ありがとうございます
ただ、問題の答えにはできないんですが…


…あと、問題について調べなおしている時に「不可能な配線」と
Googleで検索したら、クイズ大陸のこの問題がトップで出てきました。あな恐ろしや
メンテ
Re: 不可能な配線? ( No.15 )
日時: 2007/08/27 20:39
名前: REE

調べたのですが、グラフの理論で平面では無理ということが、証明されているらしいです。
キーワード「完全2部グラフ」「平面グラフ」
メンテ
Re: 不可能な配線? ( No.16 )
日時: 2007/08/28 01:43
名前: Submarin

REEさん、ありがとうございます。
こちらでも調べさせていただきました。



ういー 
なんじゃこりゃあー 
な世界でありますが、要約して皆さんにお伝えします。

それなりに噛み砕いて説明しているつもりですが、多分に幾何学的、特に位相幾何学に突っ込んだ内容なので、分からないかもしれません。(蛇足ですが、このサイトでも良く出てくる「船渡り問題」や「四色問題」もこの学問の範疇に入ります。)
筆者は理系ですが、それでも専門外で完全に理解しきったとはいえません。しかし出題者としての責任として、これを書きます。

まず、『オイラーの多面体定理』から。
膨らませると球になるような立体(多面体)について、頂点・辺・面の個数をそれぞれV,E,Rとすると、V-E+R=2が成り立ちます。
これは身近な多面体について計算してみると、成り立つのがすぐに確認されます。
(帰納法で証明できるのですが、この証明は省略します。)
この理論は、位相幾何学の基幹をなしていて、平面のグラフ(ここでは、点と線をさまざまな形で結んだ一連の図形)にも使えます。

今回の事例はグラフ理論で言うと「完全2部グラフ」というものに分類されます。
完全2部グラフというのは、端的に言うと、今回の問題の条件のことなのですが、
「辺を表す単純曲線どうしが共有する端点以外では交わらないとき(これを「平面グラフ」といいます…交わるときは「非平面グラフ」、または「多重グラフ」といいます)」
で、かつ
「すべて一方の端の点(今回は元管)がもう一方の端の点(今回は家)がそれぞれ繋がっている」
ということです。

一方の端の数をX、もう一方の端の点の数をYとすると、このようなグラフ(図)をK X,Y と示します。今回の事例では K3,3 です
さて、完全2部グラフ K3,3について、オイラーの多面体定理を適用します。
頂点が6個、辺は9本になります。ですから、面(位相幾何学でいうと「領域」)の数は5となります。

ここで、次数というものを定義します。
次数というのは、グラフ上の線で囲まれたある面(領域)に対して、その外周を成す線の数(または、グラフ全部の面に対する次数の総和)です。
(実際にはある面において、その面の外周から線が出ていて、面の中で行き止まりになる線がある場合は、それも数えます。)
適当な図を描いてみて、それぞれの領域の次数を計算すると、その図全体の総和は辺の2倍に等しくなることが分かります。(証明済みですが、ここでは略)
また、次数1となる領域は「ある点から出て、どこも経由せずにその点に戻る(ループになっている)」、次数2となる領域は「ある点から出て、1つの点を経由して戻ってくる(一組の点同士に2本で線をつないでいる)」ということも分かります。
これはつまり、次数1,2では多面体で言うところの面(領域)になりません。つまり次数は(平面グラフにおいては)3以上になるというのも分かると思います。

さて。
K 3,3について考えると、領域は5。
おのおのの領域の次数は、SANさんの書かれたように、「「家→元管→家→元管→(もとに戻る)」という「1つの閉曲線」」が全ての領域について成り立つという訳なので、4です。
つまり、全体の次数は20になります。
次数を計算すると辺の2倍に等しくなることが証明済みですから、これを2で割ると10になります。
結果、辺の数が10本ということになってしまいました。が、問題では9本なのですから、この結果は矛盾しています。
ここで、オイラーの多面体定理は恒常的な成立が確認されていますから、次数の定義に誤りがあったことになります。問題の性質上、次数が3に出来ない(「「元管→家→家」というふうになるのも、「元管→元管→家」となるのも、不可能配線」なので)ので、次数は2以下になります。

これは、平面グラフでは表せない、つまり、絶対に交点が生じることを示しています。
(平面では、面をどうやっても不可能です。点全部を面から外して、立体的に表すと、立体の内部を貫通するような線が生じます。)


…ふう。
これで分かりますでしょうか?
本編を執筆するにあたり、豊橋技術産業大学システム応用研究室内の資料(//www.system.tutics.tut.ac.jp/~fkm/math_info/math_info6.ppt#341,6,第6章 平面的グラフ,彩色,木)、
及び、「COOLEEのホームページ」内の「グラフ理論」(//coolee.at.infoseek.co.jp/graphtheory.html)
を参考にいたしました。

不可能と証明されましたので、一日ほど様子を見て閉めます。
ご解答に協力していただいた皆様には非常に感謝しております。m(_ _)m

ただ、こうなってしまうと、唯一気になるのは「出来た」という方がいらっしゃることなのですが。
メンテ
Re: 不可能な配線? ( No.17 )
日時: 2007/08/28 22:45
名前: 卵王子

やはり「不可能」と証明されてるんですね〜。
まぁ冷静に考えて、単純な平面図問題ですから、物量かけて解けなきゃやっぱりまぁ不可能ということになるんでしょうね。
「解けた」と言ってる人も多分勘違いかと。
私も解いてる途中たまに「解けた!」と一瞬勘違いすることが何度かありました。

ともあれ、興味深い問題でした。
メンテ

Page: 1 |