解答数
79
歴代 14439位 / 16,274
FILE No.12155REOPENED
方眼用紙を使って色の塗り分け
論理出題 kikki2010-05-08
事件概要
□□□□
□□□□
□□□□
□□□□
上のような４×４マスの方眼紙を赤・青・黄の３色を使って塗り分ける。上下左右に隣り合うマス同士は違う色を使わなければならない。また一回も使わない色があっても良いとする。このとき色の塗り分けパターンは全部で何通りあるか？数値だけを半角数字で入力して下さい。
|
|
|
|
|
|
|
|
手計算でも出来ないレベルではない…と思いますが(ギリで)、そこそこかなり死ぬぐらい計算量が鬼畜なので電卓使ってくれて良いです(o^-^)o。ちなみに５０００通り以上あるので間違っても１つずつ数えようとか思わないように！１００００よりは小さいんだけれどね。
出題者は２×４マス、３×４マスの場合も少し別の方法使って計算、それからエクセルで式作って検算してみて全て一致していたので、多分答えに間違いはないと思いますが、変だと思ったらコメントしてくれれば幸いです。
また解答解説で書いた方法よりももっと簡単な方法があるかもしれません、そういう方法があったらこちらもコメントで知らせてくれれば幸いです。
□□□□
□□□□
□□□□
上のような４×４マスの方眼紙を赤・青・黄の３色を使って塗り分ける。上下左右に隣り合うマス同士は違う色を使わなければならない。また一回も使わない色があっても良いとする。このとき色の塗り分けパターンは全部で何通りあるか？数値だけを半角数字で入力して下さい。
|
|
|
|
|
|
|
|
手計算でも出来ないレベルではない…と思いますが(ギリで)、そこそこかなり死ぬぐらい計算量が鬼畜なので電卓使ってくれて良いです(o^-^)o。ちなみに５０００通り以上あるので間違っても１つずつ数えようとか思わないように！１００００よりは小さいんだけれどね。
出題者は２×４マス、３×４マスの場合も少し別の方法使って計算、それからエクセルで式作って検算してみて全て一致していたので、多分答えに間違いはないと思いますが、変だと思ったらコメントしてくれれば幸いです。
また解答解説で書いた方法よりももっと簡単な方法があるかもしれません、そういう方法があったらこちらもコメントで知らせてくれれば幸いです。
封印された解答を開く
7812
ヒント１、横に２マス・縦にｎマスの場合は何通りある？
２、では横に３マス・縦にｎマスならどういう法則が成り立つ？
３、ヒント２の場合でＡ[n+1]＝３Ａ[n]＋２Ｂ[n] Ｂ[n+1]＝２Ａ[n]＋２Ｂ[n] という連立漸化式が出来る…はず。これを横四列に応用すると…。
２、では横に３マス・縦にｎマスならどういう法則が成り立つ？
３、ヒント２の場合でＡ[n+1]＝３Ａ[n]＋２Ｂ[n] Ｂ[n+1]＝２Ａ[n]＋２Ｂ[n] という連立漸化式が出来る…はず。これを横四列に応用すると…。
解説上手く纏まらない…ので箇条書きに。
ＡＡＡＡ
ＢＢＢＢ
ＣＣＣＣ
ＤＤＤＤ
上のようにマスをＡＢＣＤの４列に分けます。まずＡ列に入れる方法は３＊２＊２＊２＝２４通り。
それぞれに対してＢ列に何通り入るか考えます。このときＡに入るのが、(赤青赤青)２色だけ(ａグループとする)、(赤青赤黄)端と中が同じ色(ｂグループ)、(赤青黄赤）両端が同じ色(ｃグループ）
の３方法の入れ方によってＢ列に入るパターン数が変わってきます。
ａグループから次の列へ→ａグループが３通り、ｂが４通り、ｃが１通り
ｂグループから→ａが２通り、ｂが４通り、ｃが１通り
ｃグループから→ａが１通り、ｂが２通り、ｃが２通り出来る。
例えば「１２１２」という配列から出来る次の列は、「２１２１・２３２３・３１３１」のａグループ３つと、「２１２３・２１３１・２３２１・３１２１」のｂ４つと、「３１２３」のｃ１つ。(１２３＝青赤黄に対応)
ｂの「１２１３」からは、「２１２１・３１３１」のａ２つ、「２１３１・２３２１・３１２１・３１３２」のｂ４つ、「２１３２」のｃ１つ。
ｃの「１２３１」からは「２３２３」のａ１つ、「２１２３・２３１３」のｂ２つ、「２３１２・３１２３」のｃ２つ。
として、n列目にaグループが出来る場合に1からn列目までに入る色の組み合わせ総数をa[n]と置けば、(また同様にn列目にbグループ、n列目にcグループが来る場合をb[n]、c[n]とします。)
ａ[n+1]＝３ａ[n]＋２ｂ[n]＋ｃ[n]
ｂ[n+1]＝４ａ[n]＋４ｂ[n]＋２ｃ[n]
ｃ[n+1]＝ａ[n]＋ｂ[n]＋２ｃ[n]
ａ[1]＝６ ｂ[1]＝１２ ｃ[1]＝６
という漸化式が出来て、これにｎ＝１〜３まで代入して計算すると、
ａ[2]＝４８ ｂ[2]＝８４ ｃ[2]＝３０
ａ[3]＝３４２ ｂ[3]＝５８８ ｃ[3]＝１９２
ａ[4]＝２３９４ ｂ[4]＝４１０４ ｃ[4]＝１３１４で 答えはその合計の７８１２通り！
ＡＡＡＡ
ＢＢＢＢ
ＣＣＣＣ
ＤＤＤＤ
上のようにマスをＡＢＣＤの４列に分けます。まずＡ列に入れる方法は３＊２＊２＊２＝２４通り。
それぞれに対してＢ列に何通り入るか考えます。このときＡに入るのが、(赤青赤青)２色だけ(ａグループとする)、(赤青赤黄)端と中が同じ色(ｂグループ)、(赤青黄赤）両端が同じ色(ｃグループ）
の３方法の入れ方によってＢ列に入るパターン数が変わってきます。
ａグループから次の列へ→ａグループが３通り、ｂが４通り、ｃが１通り
ｂグループから→ａが２通り、ｂが４通り、ｃが１通り
ｃグループから→ａが１通り、ｂが２通り、ｃが２通り出来る。
例えば「１２１２」という配列から出来る次の列は、「２１２１・２３２３・３１３１」のａグループ３つと、「２１２３・２１３１・２３２１・３１２１」のｂ４つと、「３１２３」のｃ１つ。(１２３＝青赤黄に対応)
ｂの「１２１３」からは、「２１２１・３１３１」のａ２つ、「２１３１・２３２１・３１２１・３１３２」のｂ４つ、「２１３２」のｃ１つ。
ｃの「１２３１」からは「２３２３」のａ１つ、「２１２３・２３１３」のｂ２つ、「２３１２・３１２３」のｃ２つ。
として、n列目にaグループが出来る場合に1からn列目までに入る色の組み合わせ総数をa[n]と置けば、(また同様にn列目にbグループ、n列目にcグループが来る場合をb[n]、c[n]とします。)
ａ[n+1]＝３ａ[n]＋２ｂ[n]＋ｃ[n]
ｂ[n+1]＝４ａ[n]＋４ｂ[n]＋２ｃ[n]
ｃ[n+1]＝ａ[n]＋ｂ[n]＋２ｃ[n]
ａ[1]＝６ ｂ[1]＝１２ ｃ[1]＝６
という漸化式が出来て、これにｎ＝１〜３まで代入して計算すると、
ａ[2]＝４８ ｂ[2]＝８４ ｃ[2]＝３０
ａ[3]＝３４２ ｂ[3]＝５８８ ｃ[3]＝１９２
ａ[4]＝２３９４ ｂ[4]＝４１０４ ｃ[4]＝１３１４で 答えはその合計の７８１２通り！
捜査データ
正解数
6
正解率
8%
論理カテゴリ平均 19%
評価
10 pt ／ 歴代 2462位
Good / Bad
7 / 0
評価ボタンの投票
コメント
6
証言記録
正解率
8%
証言記録 (6)
kikki
(つ´∀｀):･’.::･====≡つ)´Д`):∵＞キョンシーさん
ってゆうか…マクロってそんな計算も出来るんですか…？(←マクロの使い方を良く知らない自分)。まぁでもこれで答え自体は正確に合ってるんだな…と一安心とか…。
まぁ連立漸化式作らないと解けないような問題だしてる自分もどうかとは思いますがｗ(←でも一般項求めさせる訳じゃないし、知識がないと出来ない訳ではないかな…と。)
ってゆうか…マクロってそんな計算も出来るんですか…？(←マクロの使い方を良く知らない自分)。まぁでもこれで答え自体は正確に合ってるんだな…と一安心とか…。
まぁ連立漸化式作らないと解けないような問題だしてる自分もどうかとは思いますがｗ(←でも一般項求めさせる訳じゃないし、知識がないと出来ない訳ではないかな…と。)
kikki
あるぇｗｗｗキョンシーさんのコメントが消えてた／(^o^)\
kikki
あ、あと、既に消えてしまった幽霊レスへコメントですが、「跳ね返るボールの問題」の方もそのまま残しといて貰って構わないですよー。
残り3件の証言をすべて表示
kikki
やっぱり連立漸化式の説明ぐらいしといた方が良いですね。
例えば、良く解らない生命体Ａと、良く解らない生命体Ｂが存在して、１日ごとに生命体Ａは１つのＡと２つのＢに分裂し、生命体Ｂは１つのＡと３つのＢに分裂します。(Ａ→(１日後)→Ａ＋２Ｂ、Ｂ→(１日後)→Ａ＋３Ｂ)
すると[]内を経過日数として、ＡとＢの数に間には、
Ａ[t+1]＝Ａ[t]＋Ｂ[t]
Ｂ[t+1]＝２×Ａ[t]＋３×Ｂ[t]
という関係式が成り立ちます。そしてこういう式が「連立漸化式」と呼ばれます。これを使って、例えば１日目にはＡとＢが１つずつ存在していて、１週間後にな何匹になっているか？という問題を考えてみます。(→次のコメントへ続く。)
例えば、良く解らない生命体Ａと、良く解らない生命体Ｂが存在して、１日ごとに生命体Ａは１つのＡと２つのＢに分裂し、生命体Ｂは１つのＡと３つのＢに分裂します。(Ａ→(１日後)→Ａ＋２Ｂ、Ｂ→(１日後)→Ａ＋３Ｂ)
すると[]内を経過日数として、ＡとＢの数に間には、
Ａ[t+1]＝Ａ[t]＋Ｂ[t]
Ｂ[t+1]＝２×Ａ[t]＋３×Ｂ[t]
という関係式が成り立ちます。そしてこういう式が「連立漸化式」と呼ばれます。これを使って、例えば１日目にはＡとＢが１つずつ存在していて、１週間後にな何匹になっているか？という問題を考えてみます。(→次のコメントへ続く。)
kikki
（もちろん、一般項を求める方法もあるけれども、高校数学の中でもそろそろ難しいものだと思うので説明略。）
(→前のコメントの続き)、一週間後に何匹になっているか？を求めるためには、記述した連立漸化式にｔ＝１〜６まで順番に代入していけば良いです(結構面倒臭いですが)。まずｔ＝１を代入すると、
Ａ[2]＝１＋１＝２ Ｂ[2]＝２×１＋３×１＝５ 続いてｔ＝２を代入、
Ａ[3]＝２＋５＝７ Ｂ[3]＝２×２＋３×５＝１９ これを繰り返していけば、
Ａ[4]＝２６ Ｂ[4]＝７１ Ａ[5]＝９７ Ｂ[5]＝２６５ Ａ[6]＝３６２ Ｂ[6]＝９８９ Ａ[7]＝１３５１ Ｂ[7]＝３６９１
となり、１週間後にはＡが１３５１匹、Ｂが３６９１匹居ることが解ります。
(→前のコメントの続き)、一週間後に何匹になっているか？を求めるためには、記述した連立漸化式にｔ＝１〜６まで順番に代入していけば良いです(結構面倒臭いですが)。まずｔ＝１を代入すると、
Ａ[2]＝１＋１＝２ Ｂ[2]＝２×１＋３×１＝５ 続いてｔ＝２を代入、
Ａ[3]＝２＋５＝７ Ｂ[3]＝２×２＋３×５＝１９ これを繰り返していけば、
Ａ[4]＝２６ Ｂ[4]＝７１ Ａ[5]＝９７ Ｂ[5]＝２６５ Ａ[6]＝３６２ Ｂ[6]＝９８９ Ａ[7]＝１３５１ Ｂ[7]＝３６９１
となり、１週間後にはＡが１３５１匹、Ｂが３６９１匹居ることが解ります。
kikki
こういった「連立漸化式」の考え方を使って、この出題した問題は解けるようになっています。ということです。
勿論、他の方法があるかもしれませんので、そのときはコメント宜しくです。
勿論、他の方法があるかもしれませんので、そのときはコメント宜しくです。
関連する問題
NEXT CASE
現代版推理ゲーム
未解決ファイルはこちら
▶ 未解決ファイルへ掲載内容に問題がある場合
削除依頼・お問い合わせはこちら