9796：7分割円グラフの塗り方...4色までで隣り合わない...

真白いタマスダレが瑞々し☆

問題9796(友人問)

円板の片面が、7個の合同な扇形に区切られている。赤、青、黄、緑の4本の

色鉛筆があるので、これらを使ってそれぞれの扇形に、1つずつ色を塗る。

同じ色を何度か使ってもよいし、4色すべてを使う必要はないが、隣り合った

2つの扇形には別々の色を塗る。塗り方は何通りか。ただし、ある塗り方をした

円板を回転して出来る塗り方は同じ塗り方とする。

解答

・わたしの…

最低３色必要…多くて3枚しか塗れない...

7=1+3+3=2+2+3・・・3枚のとき

7=1+1+2+3=1+2+2+2・・・4枚のとき

・133のとき…

1枚塗ったら残りの６枚は交互にしか塗れない…2通り

　・・・4C1*3C2*2=24通り

・223のとき…

・1123のとき…

・1222のとき…

6!/(2!2!2!)-5!/(2!2!)+4!/2!-3!=90-30+12-6=90-30+12-6=66

so...4*66=264通り

合計=24+48+32+264=368 通り

かなぁ…?…^^

↑

おかしかったのね…^^; Orz…

↓

・鍵コメT様からのもの Orz～

1123の32通りは少なすぎ，1222の264通りは多すぎだと思います．

1123について，ABCCDDDとして，Dの間3箇所のうち2枚になるところには，
AB,AC,BC(どれについても，順番も意味あり)のいずれかが入り，
ACやBCの場合，残り2箇所のDの間のどちらにCが入るかも別物となります．
Dの選び方4通り，Cの選び方3通りも考えて，場合の数は
4*3*(2+2*2+2*2)=120(通り)だと思います．

1222について，ABBCCDDとして，A以外の6枚の並び方は，
BCで始まるものがBCBDCD,BCDBCD,BCDBDC,BCDCBD,BCDCDBの5通り，
BD,CB,CD,DB,DCで始まるものも同数です．
Aの選び方4通りも考えて，場合の数は
4*5*6=120(通り)だと思います．

結局，24+48+120+120=312(通り).

次の方法も極めて有力です．

隣同士は同色でなく，また先頭と末尾も同色でないように
n個(n≧2)を一列に並べることを考え，並べ方の数をa[n]とする．
a[2]=4*3=12,a[3]=4*3*2=24.
また，n≧4のとき，
最後から2番目が先頭と同じ色となる並べ方は，条件を満たしてn-2個並べ，
「先頭と同じ色，他の任意の色」を追加すればよいから，3a[n-2]通り．
最後から2番目が先頭と違う色となる並べ方は，条件を満たしてn-1個並べ，
「先頭とも最後とも違う色」を追加すればよいから，2a[n-1]通り．
よって，a[n]=3a[n-2]+2a[n-1]となる．
これより順に，
a[4]=3a[2]+2a[3]=84,a[5]=3a[3]+2a[4]=240,
a[6]=3a[4]+2a[5]=732,a[7]=3a[5]+2a[6]=2184.

円形に7つ並べる並べ方1つに一列に7つ並べる並べ方7通りが対応するから，
求める数は，2184/7=312(通り).

なお，この方法ですぐに答えが出るのは，並べる個数が素数の場合だけです．
例えば8個並べる場合は，円形に並べる並べ方によって，
一列に並べる並べ方いくつが対応するかが異なり，少し面倒です．

(やどかりさんの問題834 http://blogs.yahoo.co.jp/oka_yadokary/35202790.html 参照☆)

*これが解けないんだから...やどかりさんの八分割が解けるわけがあ～りましぇん ^^;;

漸化式って思考のでっかい武器ですねぇ♪

使い切るのが難しい…^^;;;

・鍵コメH様からのもの Orz～

包除原理を使う方法もあります
1番目の色の塗り方が4通り、2番目以降の塗り方が3通りあると考え
4*3^6通りを導きます
このままだと7番目の色が1番目の色と同じ場合も数えているので
1番目と7番目が同じ色の場合 4*3^5通りをひきます
今度は1番目と6番目が同じ色の場合の分を余計にひいているので
4*3^4通りを足します

このように考えを進めていき、実質同じ盤面が7回出てくることも踏まえると
4*(3^6-3^5+3^4-3^3+3^2-3^1)/7=(3^7-3)/7=312通りとなります

*この方法には気付きたかったなぁ ^^;♪