FC2ブログ

Welcome to my blog

[答614] 一筆書きの総数

ヤドカリ

ヤドカリ



[答614] 一筆書きの総数


 上の図を一筆書きにします。

 赤の点から始める一筆書きの方法は全部で □×610 通りです。

 □に適する数は?


[解答1]

 まず、線が6本集まる点を「交差点」、線を「径路」、

 交差点において「径路」を、右回りから左回り または 左回りから右回りに変えることを「方向転換」

 ということにします。

 描き始めを右回り、隣合う2個の交差点の間の3本の「径路」の描く順序を 外側→中側→内側 に限定します。

 描き始めが左回りの場合と、3本の径路を描く順序を変えることにより、

 一筆書きの総数は、限定した場合の 2・610 倍になります。

 まず、出発点以外の「交差点」で「方向転換」がないのは、水色枠のような4種類あります。

 次に、出発点以外の「交差点」で少なくとも1回は「方向転換」がある場合、

 出発点の通過の仕方は、方向と6本の「径路」を示した、黄色枠内の上の図の6種類です。

 また、出発点以外の「交差点」の通過の仕方は、

 3回とも「方向転換」しないか、2回の「方向転換」するかのいずれかです。

 「方向転換する交差点」が1ヶ所だけの場合、黄色枠の中央に赤で示した「方向転換」をします。

 「方向転換する交差点」が2ヶ所だけの場合、黄色枠の左右に示した「方向転換」をします。

 「方向転換する交差点」が3ヶ所以上の場合、

   「方向転換する交差点」のうち、出発点の左右で一番近い所では、黄色枠の左右に示した「方向転換」を、

   その他の「方向転換する交差点」では、黄色枠の下に青で示した「方向転換」をします。

 このように、6種類の図のいずれの場合も、各「交差点」において「方向転換」するかしないかが決まれば、

 「方向転換する交差点」での「方向転換」の仕方は、一意に決まります。

 従って、全部の「交差点」で「方向転換」しない1種類を除いて、29-1 種類あります。

 一筆書きの総数は、{6(29-1)+4}・2・610=6140・610 で、□に適する数は、6140 です。

☆ n個つながった図形であれば、一筆書きの総数は 4(3・2n-1-1)・6n 通りあります。


[解答2] たけちゃんさんの解答

 赤い頂点を自宅だとして,3回お出掛けをしますが,

 右に出発して左から帰る,またはその逆(世界一周と名付ける)が1回または3回あります.

 世界一周が3回のときは,3回とも寄り道なしで,右または左回りに回るので 23=8(通り).

 世界一周が1回のときは,世界一周でないお出掛けについて,

  左にあるところ(A)まで行きそこからまっすぐ引き返すのが1回,

  右にあるところ(B)まで行きそこからまっすぐ引き返すのが1回です.

 A=Bの場合は,世界一周は寄り道なしの右または左回り,Aが9通りとなります.

 A≠Bの場合は,世界一周の際に,AB間は3回ずつ通るので,

  例えばA-C-D-Bのようにつながっていれば,A→Bと進む場合に,

  A-C-D-B-D-C-A-C-D-Bのように,CやDでは折り返さないか,

  A-C-A-C-D-B-D-C-D-Bのように,Cでは折り返し,Dでは折り返さないか,

  A-C-D-C-A-C-D-B-D-Bのように,Dでは折り返し,Cでは折り返さないか,

  A-C-A-C-D-C-D-B-D-Bのように,CでもDでも折り返すか

  の4通りができ,同様にして,A,B間に頂点がk個あれば,進み方は2k通りです.

  A,B間の頂点が0個(つまり1区間)のA,Bの選び方は8通り,

  A,B間の頂点1個のA,Bの選び方は7通りなどとなります.

 以上より,点のたどり方(つまり□に入る数)は,

  23+3!・2・(9+8・1+7・2+6・22+5・23+4・24+3・25+2・26+1・27)=6140 となります.

.

スポンサーサイト



Comments 20

There are no comments yet.
たけちゃん  
No title

世界一周が1回のときは,世界一周でないお出掛けについて,
左にあるところ(A)まで行きそこからまっすぐ引き返すのが1回,
右にあるところ(B)まで行きそこからまっすぐ引き返すのが1回です.

A=Bの場合は,世界一周は寄り道なしの右または左回り,Aが9通りとなります.

A≠Bの場合は,世界一周の際に,AB間は3回ずつ通るので,
例えばA-C-D-Bのようにつながっていれば,A→Bと進む場合に,
A-C-D-B-D-C-A-C-D-Bのように,CやDでは折り返さないか,
A-C-A-C-D-B-D-C-D-Bのように,Cでは折り返し,Dでは折り返さないか,
A-C-D-C-A-C-D-B-D-Bのように,Dでは折り返し,Cでは折り返さないか,
A-C-A-C-D-C-D-B-D-Bのように,CでもDでも折り返すか
の4通りができ,同様にして,A,B間に頂点がk個あれば,進み方は2^k通りです.
A,B間の頂点が0個(つまり1区間)のA,Bの選び方は8通り,
A,B間の頂点1個のA,Bの選び方は7通りなどとなります.

たけちゃん  
No title

以上より,点のたどり方(つまり□に入る数)は,
2^3+3!*2*(9+8*1+7*2+6*2^2+5*2^3+4*2^4+3*2^5+2*2^6+1*2^7)=6140
となります.

ヤドカリ  
No title

古い人さん、早速のコメントを有難う御座います。
仰る通り、蘇鉄の花(雄花)です。
葉も若い葉は柔らかな色をしています。

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難う御座います。
仰る通り、蘇鉄の雄花です。
蘇鉄が家の中にあると娘が婚期を逃すのですか? 知りませんでした。
こちらでは馴染みのある樹木です。

ヤドカリ  
No title

こっこちゃんさん、早速のコメントを有難う御座います。
此方では蘇鉄はよく見られます。
中央にあるのは蘇鉄の雄花です。面白い形ですね。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
仰る通り、雄花も雌花もあります。
明日は雌花の写真を使う予定です。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
やっていることは、場合分けをしているだけですが、
かなり面倒な問題だったと思います。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難う御座います。
国道220号線は、私も通ったことがありますが、
美しい海岸の風景に魅せられて、蘇鉄はあまり記憶に残りませんでした。

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難う御座います。
「輪が1組の時:8、2組:20、3組:44、4組:92」を求めるだけでも大変ですね。
うまい漸化式が出てくる保証がない段階で、ここまで求める気力は、
私にはありませんので、頭が下がります。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
難しい問題だったと思います。
いろいろ考えて頂いたようで、感謝します。

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
結局は場合分けですが、面白い表現ですね。
解答に加えさせて頂きました。

uch*n*an  
No title

う~む,tsuyoshik1942さんの漸化式,確かに一般式が解になっていますね。
こんなに簡単な式になるとは。
私の漸化式は,経路を一つたどるごとに出て来るパターンに注目したもので,
考え方は非常に単純なのですが,式はかなり面倒です。
結果が同じになる以上は導けるハズなんだけど...ちょっと導けそうにない...
時間が取れたら,とか言って最近はサッパリなんですが (^^;,再考してみようかな。

たけちゃん  
No title

tsuyoshik1942さんの漸化式を,私なりに考えてみました.

出発点をP,それ以外の任意の頂点Qとして,PからはじめてQに到達する経路を[1],
Qから最後にQに到達する経路を[2],Qから最後にPに戻る経路を[3]とすると,
PからPに戻る一筆書き[1][2][3]は,
QからQに戻る一筆書き[2][3][1]と対応付けができます.

さて,a(n+1)通りのうちには,Pで1回以上方向転換をするものと,
Pでは方向転換をしないものが含まれます.
Pで方向転換をしないものは,上記のように,QからQの経路に対応させ,
Pをなしにすることで,a(n)通りであることがわかります.

たけちゃん  
No title

以下,私の先のコメントの言い方を使います.
3回のお出掛けが世界一周3回であるもの8通りのうちには,
Pで方向転換しないものは2通り含まれ,
それ以外のa(n+1)-8通りは,
「右に行き引き返す」「左に行き引き返す」の順番を逆にすることで,
Pで方向転換をするものとしないものが一対一に対応します.

以上より,Pで方向転換をしないものの数は,
2+(a(n+1)-8)/2=a(n+1)/2-2であり,
a(n)=a(n+1)/2-2.
したがって,
a(n+1)=2a(n)+4を得ます.

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
tsuyoshik1942さんの漸化式、確かに成り立ちますが、
たけちゃんさんが書いてくれているように、
説明するとなると大変なようです。

ヤドカリ  
No title

たけちゃんさん、漸化式の理由付けを有難う御座います。
大体の流れは分かりました。理由の説明は大変ですね。
自分で試行錯誤しながら考えるしか納得できる方法はなさそうです。

tsuyoshik1942  
No title

uchinyanさん、たけちゃんさん、コメントへの反応ありがとうございます。
自分の漸化式の求式手法は邪道ですが、推定された漸化式をヒントに、それの意味を読み解くつもりでした。
たけちゃんさんの提示、解答と合わせ読み直させていただきます。

たけちゃん  
No title

さっき気付いたのですが,問題文が2回繰り返されていますね.

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難う御座います。
貴殿の書かれている漸化式が成り立つことは[解答1]の一般化の式から
明らかなのですが、漸化式自体の意味づけは難しいです。
解答を頂き、私も考えたのですが、うまくまとまらず、
そのままになってしまってい、申し訳ありません。

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
早速、不要部分を削除しました。
不注意なコピペをしてしまいました。