スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
-- : -- : -- | スポンサー広告 pagetop

puzzle me

正八面体一筆書きパズル

前期の研究発表が昨日ようやく終わったので息抜きに。あとは院試だけだー。
幾何というよりはグラフの問題ですね。
解答

結論は最後に。あえて回り道します。その方が面白いから。

まず、平面上で合同な正三角形が辺を共有してたくさんくっついた集合体を考えてみます。
正八面体の展開図の一般化みたいなイメージをぼんやり持ちつつ。
そして、外周に方向を決めてやります。ここでの方向は右回りか左回りのどちらかです。


T[n]
(※図形の辺に付した矢印は辺の方向を表しています)

こんなかんじの、外周に方向のついた多角形の集合を考えるわけです。
この多角形のうちn個の正三角形で構成されるものの集合をT[n]とします。
T[1]が問題で言われている「赤く塗る面」に対応します。
n=1, 2, 3 まではT[n]は(外周の向きを除いて)一意に決まりますが、
T[4]以降は一般に複数の形を持ちます。

さて、t∈T[n]は外周だけ方向が決まっている状態です。
次にこのtの各辺に対する「方向付け」、つまり内部の三角形の全ての辺に対して
各々方向をを決めてやることを考えます。

そしてその中にT[1]、すなわち三辺全てが同じ回転方向を向いたものが
ひとつも存在しないような組み合わせがあるかどうかがここでの興味です。


まずT[2]を考えてみましょう。

T[2]

方向がついていないのは真ん中の一辺のみです。
しかしこれを下向きとすると左側の三角形が右回りでT[1]の要素となり、
逆に上向きとすると今度は右側の三角形がT[1]の要素となります。


同様にT[3]についても

T[3]

青線を下向きとすると左側の三角形が
緑線を上向きとすると右側の三角形が
青線を上向きかつ緑線を下向きとすると真ん中の三角形が
それぞれT[1]の要素となります。


T[1]の要素ができないように方向付けをしようと試みると、
三角形の二辺が同じ方向に定まっている場合、
残り一辺の方向が自動的に決まるということです。
T[n]には外周の方向が定まっているので、三辺のうち二辺が外周の一部になっている「突き出た」三角形の残り一辺の方向は自動的に決まります。

そして自動的に方向が決まる辺を順次定めていくと必ずどこかの辺で向きが衝突してしまう、つまりT[1]に含まれる図形ができないという制約を保ったまま全ての辺に向きをつけることができなくなります。

T[4]の場合は3種類ありますが、同様に考えればどれも必ずT[1]を含むことがわかります。
T[4]



一般のnでも同じことが言えそうな雰囲気です。
そこで次の命題を提示します。


命題A:
任意のnについて
T[n]に含まれる多角形の内部の三角形の全ての辺に方向を定めたとき
その中に少なくとも一つT[1]に含まれるものが存在する


この命題の真偽は次の記事のネタにするとして、ここでようやく本題に入ります。


問題
「赤く塗る面(=T[1])が一つも存在しないような、正八面体の一筆書き方法はあるでしょうか」


正八面体を一筆書きすると、その過程で少なくとも一つは単純な閉路(一度通った点は通らないようなループ)ができます。(一筆書きなのだから、最初に出発した頂点を再び通る。その途中で同じ点を2度以上通るなら、その点から出発してその点に戻ってくるまでの部分ループを(再帰的に)考えればよい)

そしてその閉路は、適当な展開図上でT[n]の要素となるものです。

また正八面体の頂点は6個であり、6個の点から構成できるのはT[4]の要素までです。
これはn≧5について、T[n]に含まれる多角形を具体的に考えてみれば明らかでしょう。

つまり、正八面体の一筆書きの中には、必ずT[n](n≦4)の多角形が含まれるのです。
先に示したとおり、n≦4のときT[n]の要素の内部には必ずT[1]の要素が存在しますから、
問題の答えはNo。そのような一筆書きは存在しないことがわかります。
スポンサーサイト
18 : 04 : 46 | misc. | トラックバック(0) | コメント(2) pagetop
<<展開 | ホーム | オンラインゲーム 2.0>>
コメント
こんにちは この問題に関連して 教えてください 8面体の稜線一筆の一例でみると  面の各三角形での運筆の向きは三辺で同じである そして隣り合った面のその向きは交互に変わる 各面の3辺の運筆は一つを除いて(1-2-3の如く)順番である。
これは 一筆可能な すべて経路について言えますか? ちなみに経路は幾つあるのでしょうか ? 
by: はんにゃ * 2008/04/29 13:35 * URL [ 編集] pagetop
ごめんなさいずっと放置してました...!
多分もう見てないと思いますが一応回答しておくと (条件の解釈が当っているか自身ありませんが) すべての経路に対して成り立つことは無いと思いますよ。少なくとも一番最初の条件が全ての辺に対して成り立つとは限らないので。

経路の数ですが、各頂点を区別するかしないかで話が変わってきます。区別する場合は簡単ですが、しない場合はちょっと面倒かもしれません。
by: しむかっぷ * 2008/09/03 00:37 * URL [ 編集] pagetop

コメントの投稿














管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://arith.blog70.fc2.com/tb.php/18-066c2e31
この記事にトラックバックする(FC2ブログユーザー)
| ホーム |

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

プロフィール

しむかっぷ

Author:しむかっぷ
狐の抜け殻

最近の記事

最近のコメント

最新トラックバック

月別アーカイブ

 全記事の一覧

カテゴリー

リンク

リンクフリー&アンリンクフリー

ブログ内検索

RSSフィード

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。