アットランダム≒ブリコラージュ

8399：4色以内で隣り合わない8カ所塗り...

問題8399・・・やどかりさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/35202790.html より Orz〜

　図のように、円を扇形に８等分し、黄･緑･青･赤の４色の全部または一部で塗り分けます。

　隣り合う扇形は異なる色で塗るものとし、回転して同じになるものは同じものと見なすとき、

　塗り分け方は全部で何通り？

解答

上記サイト http://blogs.yahoo.co.jp/oka_yadokary/35222344.html より Orz〜

[解答1]

　まず、回転して同じでも異なるものと考え、円を扇形にｎ等分したものに塗る方法の数を a_n とします。

　特定の扇形から順に左回りに異なる色を塗るものとすれば、

　最初と最後の色が異なる場合と同じ場合を含めて a₈＋a₇＝4･3⁷ ，a₇＋a₆＝4･3⁶ ，a₆＋a₅＝4･3⁵ ，

　a₅＋a₄＝4･3⁴ ，a₄＋a₃＝4･3³ ，a₃＋a₂＝4･3² ，a₂＋a₁＝4･3 ですので、

　a₈＋a₁＝4･3⁷−4･3⁶＋4･3⁵−4･3⁴＋4･3³−4･3²＋4･3＝4･3｛1−(−3)⁷｝/｛1−(−3)｝＝3(1＋3⁷)＝6564 、　

　a₁＝0 ですので、a₈＝6564 になります。

　以下、回転して同じ塗り方になるものを同一のものとして考えると、

　図Ｂのように 180ﾟの回転で同一になるものは、

　１色を４ヶ所に塗り １色を使わない場合の 4･3＝12 通りと、

　４色とも塗る場合は円順列と同様の (4−1)!＝6 通りの合計 18通り、

　図Ｃのように 90ﾟの回転で同一になるものは、２色の選び方で、₄Ｃ₂＝6 通り、

　図Ａのように 360ﾟの回転でしか同一にならないものは、(6564−18･4−6･2)/8＝810 通りです。

　よって、求める場合の数は、 810＋18＋6＝834 通りになります。


[解答2]

　まず、回転して同じでも異なるものと考え、円を扇形にｎ等分したものに塗る方法の数を a_n とします。

　左下図が円を扇形にｎ等分したものとして、矢印の扇形を最後に塗るものとします。

　最後に塗る扇形の両側の色が異なる場合、他の部分の塗り方は a_n-1 通り、

　最後に塗る扇形の両側の色が同じ場合、他の部分の塗り方は a_n-2 通りですので、

　最後に塗る色の決め方を含め、a_n＝2a_n-1＋3a_n-2 が成り立ちます。

　a₁＝0，a₂＝12 だから a₃＝2a₂＋3a₁＝24，a₄＝2a₃＋3a₂＝84，a₅＝2a₄＋3a₃＝240，a₆＝2a₅＋3a₄＝732，

　a₇＝2a₆＋3a₅＝2184，a₈＝2a₇＋3a₆＝6564 です。　( 漸化式を解くと a_n＝3ⁿ＋3･(−1)ⁿ です )

　円を扇形に８等分する場合、右下図のように、

　a₈−a₄＝6564−84＝6480 通りが、８通りずつ回転して同じになり、

　a₄−a₂＝84−12＝72 通りが、４通りずつ回転して同じになり、

　a₂＝12 通りが、２通りずつ回転して同じになるので、

　求める場合の数は、 6480/8＋72/4＋12/2＝810＋18＋6＝834 通りになります。

*面白い問題だったのに...けっきょく辿り着けず…^^;;

重複を含めた場合から、そうでない場合を引いて考えてみたんですが…

2分割を4色以下で塗る…4*3=12=f(2)
3分割…4*3*2
これは、4*3^2-f(2)=36-12=24=f(3)
4分割…4!+4C3*2*3!+4C2*2!=24+48+12=84
これは、4^2*3^2-2*f(3)-f(2)=144-2*24-12=84=f(4)
5分割…4^2*3^3-2*f(4)-f(3)=4^2*3^3-2*84-24=240=f(5)
6分割…4^2*3^4-2*f(5)-f(4)=4^2*3^4-2*240-84=732=f(6)
7分割…4^2*3^5-2*f(6)-f(5)=4^2*3^5-2*732-240=2184=f(7)
8分割…4^2*3^6-2*f(7)-f(6)=4^2*3^6-2*2184-732=6564

ここから、回転して重複する場合わけが気が遠くなるように思えて…座礁…^^;;

[解答2]をみて納得できました☆

8は…2,4回転の重複を除けばいいので...
a(8)は...2枚の組み合わせが1枚と見れば(a4), 4枚の組み合わせを1枚と見れば(a2)・・・(a4)を2回(2*45°=90°)回せば(a2)を1回(90°)を含んでる...
a(4)は…2枚の組み合わせを1枚と見ればa(2)
so...
((a8)-(a4))/8+((a4)-(a2))/4+(a2)/2
=((a8)+(a4)+2*(a2))/8
=(6564+84+2*12)/8
=834

ってことだったのねぇ...

柔らかい発想がなきゃ無理ですね…^^;;

いやぁ〜面白い☆

お気に入り♪

☆今年もいっぱい楽しませて頂き感謝〜m(_ _)m〜☆

8398：5色で塗り分け...

問題8398・・・算チャレ！！ http://www.sansu.org より Orz〜

上の図を、５色で塗り分けることにします。

（「塗り分ける」とは、隣り合った場所を別の色で塗ることをさします）

 

このとき、塗り分け方は何通りあるか、求めてください。

ただし、５色すべてを使わなくても良いものとします。

 

*問題公開から１１時間ほどの間、「５色すべてを使わなくても良い」の注意書きがなく、２通りの問題文の解釈が可能な状態となっておりました。というわけで、それまでの分につきましては、どちらの解釈（５色以内で塗り分ける場合と、５色すべてを使用するとした場合）でも正解とさせていただくことにいたしました。

解答

ライブ問にてまたいずれ ^^

5色すべての場合でやっと入れましたぁ ^^;v