塗分けの問題です。（図の書き方が判らないので文章で…）
正六角形の各辺の周りを同じ大きさの直角三角形で囲んで、一回り大きな正六角形を作ります。初めの六角形をG、周りの直角三角形をA〜Fとします。隣り合う部分は同じ色では塗れないとします。色は今7色用意されています。
(1)7色全てを使っての塗分け。（マスを区別しない）
(2)7色全てを使っての塗分け。（マスを区別する）
(3)3色を選んでの塗分け。（マスを区別する）
(4)4色を選んでの塗分け。（マスを区別する）
(5)5色を選んでの塗分け。（マスを区別する）
(1)は真ん中のGを決め、回りは円順列として計算し840通り。
(2)は単純に7!＝5040通り
(3)は7C3で3色選び、そのうちGが3通り、残り2色で6箇所を塗り分けるには3マス・3マスの組み合わせだけなので2通り。したがって35*3*2＝210通り、 で解答とも合っていたのですが、(4)、(5)が太刀打ちできませんでした。解説をお願い致します。ちなみに(4)＝7560通り、(5)＝50400通りだそうです。よろしくお願い致します。
|
No.22058 - 2013/07/26(Fri) 20:04:38
| ☆ Re: / 犬好きおやじ | | | 直角三角形の斜辺が元の六角形の各辺に接して、その斜辺のはみ出した部分が次の直角三角形の短辺と重なります。（これで分かりますか？）
|
No.22060 - 2013/07/26(Fri) 20:47:48 |
| ☆ Re: / ＩＴ | | | No.22061 - 2013/07/26(Fri) 20:52:07 |
| ☆ Re: / ＩＴ | | | (4)4色を選んでの塗分け。（マスを区別する）
7色から4色を選んで順に並べる方法は、7*6*5*4 通り
先頭の色は、元の六角形に塗る。
のこりの３色の塗り方は、３色を１、２、３とし、最初に出現し塗る順番をこの順を崩さず塗る方法は
A-B-C-D-E-F(樹形図の代わりです）
1-2-1-2-1-3
*-*-*-*-3-2
*-*-*-3-1-2
*-*-*-*-*-3
*-*-*-*-2-3
*-*-3-1-2-3
*-*-*-*-3-2
*-*-*-2-1-2
*-*-*-2-1-3 ＜※追加
*-*-*-*-3-2
の１０通り ＜※
よって求める塗り方は、7*6*5*4*10＝8400通り ＜※ angel さんのご指摘により修正しました。
|
No.22062 - 2013/07/26(Fri) 21:20:00 |
| ☆ Re: / ＩＴ | | | (5)5色を選んでの塗分け。（マスを区別する）
7色から5色を選んで順に並べる方法は、7*6*5*4*3 通り
先頭の色は、元の六角形に塗る。
のこりの4色の塗り方は、4色を１、２、３、４とし、最初に出現し塗る順番をこの順を崩さず塗る方法は
A-B-C-D-E-F(樹形図の代わりです）
1-2-1-2-3-4
******3-1-4
********2-4
********4-2,3
****3-1-2-4
********3-4
********4-2,3
******2-1-4
********3-4
********4-2,3
******4-1-2,3,4
********2-3,4
********3-2,4
の２０通り,よって求める塗り方は7*6*5*4*3*20＝50400通り
|
No.22064 - 2013/07/26(Fri) 21:49:16 |
| ☆ あれ? / angel | | | (4)は答えが違うのでは…?
ITさんの樹形図で言うと、
> *-*-*-2-1-2
> *-*-*-*-3-2
最後のこの2行の間に“*-*-*-*-*-3”が入ると思います。
結局、×9 ではなく ×10 で 8,400通り
|
No.22065 - 2013/07/26(Fri) 23:34:41 |
| ☆ 別解(4) / angel | | | 私の考えた(4)の別解は次の通りです。…あんまり汎用的とは言えないかも知れませんが。
中心の周りの6マスで3色なので、同じ色を塗るマスの数は、3-2-1 もしくは 2-2-2
マスに 1〜6 の ID を振ったとして、その内訳は
3-2-1
同色3マス: 1,3,5 もしくは 2,4,6 の2通り
同色2マス: いずれの場合も残り3マス中2マスで3通り
計2×3=6通り
2-2-2
マス1と同色のマスで区別
3or5: 前者は 2,5が同色、後者は 3,6 が同色と一意に決定、計2通り
4: 2と同色が5,6の2通り
計2+2=4通り
ということで、色の内容まで考えない配置で6+4=10通り
後は色の組み合わせも考えて、10×7×6×5×4=8,400通り
|
No.22066 - 2013/07/26(Fri) 23:46:08 |
| ☆ (5)別解 / angel | | | 他の色数での数値が出ているので、余事象で考えてみます。
まず、残る「7色中6色」ですが、
周囲6マス中同色となる2マスの組み合わせ
… 6C2-6 = 9通り
から、
9×7P6 = 45,360
とあっさり求まります。
続いて、全体となる「7色中任意」です。
これは、
・中央が7通り
・周囲の6マス中、一番上は6通り
・その右隣は5通り
・その右隣りも5通り
…
・最後の残りだけ4通り
で、7×6×5^4×4 と言いたい所ですが、これでは足りません。最後のマスの両隣が同色で、最後が×5になる分の+1が抜けているからです。不足分は、
・中央が7通り
・最後に残るマスの両隣が同色で6通り
・同色のマスの各隣が5通りずつ
・さらにそれらに挟まれたマスが4通り
で、7×6×5^2×4(×+1) と。でもまだ足りません。
さらに
・中央が7通り
・最後に残るマスの両隣が同色で6通り
・同色のマスの各隣がさらに同色で5通り
で、7×6×5(×+1×+1) も足してやっと終わりです。
結局、
7×6×5^4×4 + 7×6×5^2×4 + 7×6×5 = 109,410
が全体となります。
なので、7色中5色のケースは、
109,410 - 210 - 8,400 - 45,360 - 5040 = 50,400通り
と計算できます。
|
No.22067 - 2013/07/27(Sat) 00:00:34 |
| ☆ Re: / ＩＴ | | | > (4)は答えが違うのでは…?
angel さんのおっしゃるとおりです。ありがとうございました。私の解答は修正しました。
|
No.22068 - 2013/07/27(Sat) 00:32:07 |
| ☆ Re: / ＩＴ | | | (5)の別解
一般に、輪状に並んだ区別の付くｍ個のものにｎ種以内の色を隣り合う色は異なるように塗る方法は
{(n-1)^m}+{(-1)^m}(n-1) 通りである。(証明は２つ下に)
４色を決めたとき,周りの６つの三角形をその４色以内で塗る方法は, 3^6+{(-1)^6}×3=732通り
３色を決めたとき,周りの６つの三角形をその３色以内で塗る方法は, 2^6+{(-1)^6}×2=66通り
２色を決めたとき,周りの６つの三角形をその２色(以内)で塗る方法は, 1^6+{(-1)^6}=2通り
したがって ある４色を決めたとき
周りの６つの三角形をその４色ちょうどで塗る方法は, 732-(4C3)×66+(4C2)×2=480通り
７色から中心の色の選び方は７通り、残りの６色から４色を選ぶ方法は6C4通り
よって求める塗り方は, 7×(6C4)×480=50,400通り。
|
No.22069 - 2013/07/27(Sat) 01:11:56 |
| ☆ Re: / ＩＴ | | | (4)の別解
３色を決めたとき,周りの６つの三角形をその３色以内で塗る方法は、2^6+{(-1)^6}×2=66通り
２色を決めたとき,周りの６つの三角形をその２色(以内)で塗る方法は、1^6+{(-1)^6}=2通り
したがって ある３色を決めたとき
周りの６つの三角形をその３色ちょうどで塗る方法は、66-(3C2)×2=60通り
７色から中心の色の選び方は７通り、残りの６色から３色を選ぶ方法は、6C3通り
よって求める塗り方は、7×(6C3)×60= 8400通り。
|
No.22070 - 2013/07/27(Sat) 01:25:28 |
| ☆ Re: / ＩＴ | | | 輪状に並んだ区別の付くｍ個のものにｎ種以内の色を隣り合う色は異なるように塗る方法は
{(n-1)^m}+{(-1)^m}(n-1) 通りである。
(証明)
まず、一列に並べた場合の塗り方の数をa(m)とおく、※以下、表記を簡単にするためnは固定して考える
先頭n色、（その後）×(n-1)色×(n-1)色×…×(n-1)色なので
a(m)=n(n-1)^(m-1)通り
このうち、先頭と末尾の色が同じものの数をb(m)とおく。※求める塗り方の数は、a(m)-b(m)通りである。
m+1個の列をn種以内の色を隣り合う色は異なるように塗る方法のうち
先頭と末尾が同じ色であるものは、
m個の列をn種以内の色を隣り合う色は異なるように塗る方法のうち
先頭と末尾が異なる色であるもの末尾の次に先頭と同じ色を追加したものと考えることができるので
b(m+1)=a(m)-b(m),そしてb(1)=n,b(2)=0である。
b(m+1)+b(m)=a(m)= n(n-1)^(m-1)
この漸化式を解くと、b(m)=(m-1)^(n-1)+{(-1)^(m-1)}(n-1)
よって、a(m)-b(m)= {(n-1)^m} + {(-1)^m}(n-1)…求める塗り方の数
|
No.22072 - 2013/07/27(Sat) 08:15:17 |
| ☆ Re: / 犬好きおやじ | | | 皆さんありがとうございました。大変よくわかりました。(4)の問題については私も8400通りになったのですが、解答が7560通りとなっていて、結局その先に進めずの状態でした。本当にありがとうございました。
|
No.22074 - 2013/07/27(Sat) 09:56:18 |
| ☆ Re: / ＩＴ | | | > (4)の問題については私も8400通りになったのですが、解答が7560通りとなっていて、結局その先に進めずの状態でした。
その問題集の解法は、どんなものでしたか？参考までに教えてください。
|
No.22075 - 2013/07/27(Sat) 10:58:59 |
| ☆ 模範解答もね… / angel | | | > 解答が7560通りとなっていて、結局その先に進めずの状態でした。
模範解答も間違えることが少なからずあるので、あまり信用してはいけない、というのが私が小〜高時代に得た教訓ですね…。
※「模範解答」を「先生」や「教科書」に置き換えても良い。
だからといって端から疑うことはしませんけど。
対策はまあ、色んな角度から検証してみる ( できる力をつける ) しかないのでしょう。( 別解を考えてみるとか、検算してみるとか )
|
No.22077 - 2013/07/27(Sat) 11:26:00 |
| ☆ Re: / 犬好きおやじ | | | 解説はなく、解答のみしかついていません。それで仕方なく、みなさんにお願いいたしました。ありがとうございました。
|
No.22079 - 2013/07/27(Sat) 12:56:46 |
| ☆ Re: / ＩＴ | | | > 解説はなく、解答のみしかついていません。
なるほど、了解しました。
入試対策ならその問題集は使わない方がいいかも知れません。時間のムダになる恐れがあるので。
|
No.22080 - 2013/07/27(Sat) 13:22:21 |
|
