平成１９年１１月２５日

[流れ星]

　　　　　第1９９回数学的な応募問題解答NO2

　　　　　　＜解答募集期間：１１月４日〜１１月２５日

［旗の色塗り］

皆さん、次のような旗の４つの部分に、何色かのどれかを塗って、同じ色のものが隣り合わないようにする方法は何通りあるかを考えてください。　

問題１：２種類の色で塗り分けるとき。

問題２：３種類以下の色で塗り分けるとき。

問題３：４種類以下の色で塗り分けるとき。

問題４：５種類以下の色で塗り分けるとき。

問題５：ｎ種類以下の色で塗り分けるとき。ただし、ｎ≧２の自然数とする。

NO8「kasama」 11/17 03時06分受信 更新11/25

【問題１】　の2色で塗り分けると、次のようになります。

よって、2通りです。

【問題２】　の3色で塗り分けると、次のようになります。

よって、18通りです。

【問題３】　の4色で塗り分けると、次のようになります。

よって、84通りです。

＜水の流れ：問題４は容量のため割愛させていただきます。全部で２６０通りあります。＞

【問題５】　色を塗る順序は問題ではないので、右のように塗る順序を固定して、�Aと�Bを同じ色で塗るかどうかで場合分けして考えます。
・�Aと�Bを同じ色で塗る場合
　�@の色はn通り
　�A�Bの色は�@以外だから、n-1通り
　�Cの色は�A�B以外だから、n-1通り
　よって、n(n-1)²です。
・�Aと�Bを異なる色で塗る場合
　�@の色はn通り
　�Aの色は�@以外だから、n-1通り
　�Bの色は�@�A以外だから、n-2通り
　�Cの色は�A�B以外だから、n-2通り
　よって、n(n-1)(n-2)²です。
以上から、n(n-1)²+n(n-1)(n-2)²=n(n-1)(n²-3n+3)通りです。

＜kasamaさんのコメント：今回も面白い問題ですね。あまり自信がないのですが、できた気がするので解答をお送りします。意図したやり方かどうかはよくわかりません。漸化式によるアプローチで取り組むのでしょうか。＞

＜水の流れ：皆さんはいろいろな方法で取り組んであります。
　解答の鮮やかさに驚愕しています。時間を割いていただいたことに恐れ入ります。＞