つーさのくーかん

昨日の記事を書いてからあるパズルに挑戦してた。

これ問題。
http://d.hatena.ne.jp/rrrrrrevy/20060320#1142793866

以下私なりの解答と考察。
26日に解答発表とのことなので、こんな記事書いちゃマズいかもしれませんが。

自分で挑戦してみる方は続きを読まないでください。

まずは、私が解答を出すまでの過程。

さて、どっから手を付けていいかもわからない。
しばらく図とにらめっこω

そして気づいたことは

命題の経路を満たすには、中心の点も1度だけ通る。
そのため、中心の点から内側円上の各点に伸びている8本の線分のうち、
2本だけが必ず選ばれる。

というわけで、もっとも内側の線分の選び方に着目して"数え上げ"ることにしました。

便宜上点に名前付けますか。
上方向を0として時計回りに、外0～外7、内0～内7、中で。

とりあえず、上を定めるために、外0-内0を結んでおきました。経路の取り方は。

外0 - 内0-中-内1 - ... → パターン01
外0 - 内0-中-内2 - ... → パターン02
外0-内0 - 内1-中-内2 - ...→ パターン12
外0-内0-内1 - 内2-中-内3 - ...→ パターン23 
外0-内0-内1-内2 - ... - 内6-中-内7 - ...→ パターン67

と、まぁ、こんな感じ。
後は、ひたすら経路図を書いて確かめるω

やってる途中で、

内(偶数)-中-内(偶数) や 内(奇数)-中-内(奇数)の接続経路は存在しない

ことにも気づきました。

んで、実際に、地道にひたすら経路図を書いて、パターン列挙してみると、

01,03,03,05,05,07,07, 12,14,16, 23,25, 34,36, 45, 56

なんてでてきちゃったわけですよ。

法則性ないのか？

そう思いきや。
じーっと自分の書いた経路図を眺めていると
03の一方は回転すると27と見なせる、
05の一方は回転すると47と見なせる、
07の一方は回転すると67と見なせる、
ことに気づきました。

# "上を定める取り決め"がちょっと不十分だったようで、
# 今はもーちょっとまともな上を定めるときのルールを見つけたので後述。

で。

出現するパターンを列挙。
01,03,05,07, 12,14,16, 23,25,27, 34,36, 45,47, 56, 67。
(4+3+3+2+2+1+1)通り * 各種回転形 8通り = 128通り

なんて出したわけです。

偶数-奇数ペアと奇数-偶数ペアが、見事に全部列挙されています。
これならなかなか信憑性がありそうだ、と、コメントを叫んで終了。
ここまでが昨日の話。

んで、今日。
れびたんは違うアプローチから128という数字を出してることがわかりました。
んで、メッセンジャでもって「どんな方法でやったー？」なんて話をしました。
とりあえず、お互いの手をバラして「合ってるっぽいね」なんてやってから、「一般化できねーか？」という話に。

試しに、四角形と六角形について数え上げを試みることになりました。
とりあえず、自分は自分の方法で、またねちねちと経路図を書いてみました。
結果は、四角形が16ルート、六角形が54ルート。
それぞれ、

01,03,12,23 の (2+1+1) * 4 = 16通り
01,03,05,12,14,23,25,34,45 の (3+2+2+1+1) * 6 = 54通り

ってな具合で、とても帰着できそうな感じです。

じゃあもう、10角形は

(5+4+4+3+3+2+2+1+1) * 10 = 250通り

ですよね？
れびたんもれびたん流のやり方で、250を導いていたのでやり方は正しそうです。

角の数をnとしたとき、ルートの数Sは
  S = (n/2)^2*n

ってことで。

後は証明かねぇ、ってとこで今日は寝るかー、ここまで。

んで、ここからが寝た後(？)。
とりあえず、この数え方が正しいことを証明する方向でいけるかなぁ？
完成してるとは言えないかもしれない。

角の数をnとおく。

とりあえず、経路を定めるにあたって、経路図の向きを定める。
外0-外(n-1) と 内0-内(n-1) の2区間を「いずれも結ばない」ことで上方向を固定できる、はず。
同じ方位に属する外線と内線のいずれもが結ばれない方位　が8方位のうち必ず1方位ある。
0方位の場合は真ん中の点に行けず、2方位以上の場合は島ができることになる。
つまり、その1方位を固定することで向きが固定されたことに、なるよね？
なんか、わかりにくい説明ω

一端を中心点とするn区間のうち、いずれか2区間を選ぶ。
このとき、「内(偶数)-中-内(偶数)」と「内(奇数)-中-内(奇数)」については命題を満たすルートが現れず、
その他の場合に置いてルートがただ一つ決まる。(この辺が不足かも。やってみるとそうなるんだけど。)

つまりルートの取り方は、

{ 最初の線の選び方 n * 2本目の選び方 n/2 } / 2!(組み合わせだから)

となる。
んで、そのそれぞれのルートに、「結ばれない方位」を回転移動したn通りがあるので、

(n*n/2)/2*n = (n/2)^2*n
n=8 のとき (8/2)^2*8 = 128 通り

ってことで、いいんかねぇ。

あー、なんて頭の悪そうな証明なんだろうか。
まぁ、こんな風に納得しています、私は。

さて、とりあえず今日はここいらで。