平成１９年１１月２５日

[流れ星]

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

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

［旗の色塗り］

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

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

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

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

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

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

NO1「uchinyan」11/04 15時43分受信

「uchinyan」11/05 12時14分受信 更新11/25

第１９９回数学的な応募問題

［旗の色塗り］

基本的に同様の考え方でできるので，まずは，一般的に解いてしまいましょう。
ただし，題意が今一つピンとこなかったので，若干自分なりの解釈を入れての解答になっています。

旗はポールに固定されているので，上下左右の区別があることに注意します。

(というか，そのように解釈しました。ただし，裏表は言及されていないので考えないと解釈しました。)

すると，次のように考えられます。

まず，左上を塗るのに n 通り。そして，

・右上と左下が同じ色の場合

これは n-1 通り。このとき，右下は右上と左下以外であればいいので n-1 通り。

結局，(n-1) * (n-1) = (n-1)^2 通り。

・右上と左下が異なる色の場合

これは，右上が n-1 通り，左下が n-2 通り。このとき，右下は右上と左下以外であればいいので n-2 通り。結局，(n-1) * (n-2) * (n-2) = (n-1) * (n-2)^2 通り。

したがって，最初の n 通りをかけて

n * {(n-1)^2 + (n-1) * (n-2)^2} = n(n-1)(n^2 - 3n + 3) 通り，n >= 2　になります。

問題１：

n = 2 の場合なので，2 通り。

問題２：

n = 3 の場合なので，18 通り。

問題３：

n = 4 の場合なので，84 通り。

問題４：

n = 5 の場合なので，260 通り。

問題５：

n(n-1)(n^2 - 3n + 3) 通り。

(感想)

今回は題意が今一つ分からず，とんでもない勘違いをしているかもしれません．．．

どうも，場合の数は文章による説明の問題となることが多いので，その解釈を間違いやすくて苦手です。

どうかなぁ．．．

NO2「新俳人澄朝」11/05 11時15分受信 更新11/25

NO3「Toru」 11/05 15時39分受信 更新11/25

左上、右下、右上、左下の順に塗ることにします。

問題１　2x1x1x1=2（通り）
問題２　右下が左上と同じときと違う時で分けて
　　　　3x1x2x2+3x2x1x1=18 （通り）
問題３　右下が左上と同じときと違う時で分けて
　　　　4x1x3x3+4x3x2x2=84（通り）
問題４　右下が左上と同じときと違う時で分けて
　　　　5x1x4x4+5x4x3x3=260 （通り）
問題５　右下が左上と同じときと違う時で分けて
　　　　nx1x(n-1)x(n-1)+nx(n-1)x(n-2)x(n-2)=n(n-1)(n^2-3n+3) （通り）

　細かいことですが、４箇所しかないものを５色以上ででぬりわけるというのも、な
にか変ですから、例えば、「n色の絵の具があって、図のような旗をとなりが同じ色
にならないように塗る時、何通りできるか」という設問の方が自然な感じがします。
　

NO4「ぐーてん」11/05 17時49分受信 更新11/25

旗を同じ色が隣り合わないように塗り分ける方法は，以下の4パターンである．

問題1

2色で塗り分ける場合に使用できるパターンは�@のみで，A，Bに2色を割り当てればよいので，求める方法の数は通り．

問題2

3色以下で塗り分ける場合に使用できるパターンは�@，�A，�Bの3パターン．�@の場合はA，Bに3色から2色選んで割り当て，�A，�Bの場合はそれぞれA，B，Cに3色を割り当てればよいので，求める方法の数は，通り．

問題3

4色以下で塗り分ける場合に使用できるパターンは全4パターン．�@の場合はA，Bに4色から2色選んで割り当て，�A，�Bの場合はそれぞれA，B，Cに4色から3色選んで割り当て，�Cの場合にはA，B，C，Dに4色を割り当てればよい．

従って求める方法の数は，通り．

問題4

5色以下で塗り分ける場合も同様に全4パターン使用でき，それぞれの場合に使用できる色を5色の中から選んで割り当てればよいので，求める方法の数は，通り．

問題5

の場合は�@〜�Cの全パターンが使用でき，問題3，4と同様に考えて，

またこの解にを代入すると問題1，2で求めた解と一致するので，求める方法の数は通り．

MNO5「bear56」　11/05 18時44分受信 更新11/25

「旗の色塗り」についての解答です．全てを数え上げようとすると，O(n^4)で増加するので，大変です．
２色以上なので，(n-1)の場合と，(n-2)の場合と，残りの場合からダブりを除いた組み合わせの合計を
求めるのが正当なのでしょうね．
考えてみましたが，説明がこじつけの様になってしまうので，やめておきます．
まじめにグラフ理論とかネットワーク問題とかやってれば，見通しが良いのでしょうね．以下，解答です．

旗の4つの部分を次のように見る．
A-B
| |
D-C

☆問題１

２種類の色を1,2とすると，
ABCDは，
1212
2121の，２通り．

☆問題２

３種類の色を1,2,3とすると，
ABCDは，
1212
1213
1232

以降は類推して，
３×２×３の１８通り．

☆問題３

４種類の色を1,2,3,4とすると，
ABCDは，
1212
1213
1214
1232
1234
1242
1243

以降は類推して，
４×３×７の８４通り．

☆問題４

５種類の色を1,2,3,4,5とすると，
ABCDは，
1212
1213
1214
1215
1232
1234
1235
1242
1243
1245
1252
1253
1254

以降は類推して，
５×４×１３の２６０通り．

☆問題５

ｎ種類の色を1,2,3,...,nとすると，

問題１〜４から類推して，
n(n-1)[(n-1)(n-2)+1]通り．（ただし，n≧2）

別の類推から，
n[(n-1)+(n-2)+n(n-2)^2] = n(n-1)[(n-1)(n-2)+1]
も得ていますが，説明し切れません．

NO6「kashiwagi｣11/06 07時55分受信 更新11/25

199回問題

問1.

2色の場合対角線上が同じ色なので2通りである。

問2.

3色の場合、2マスに塗る色は3種類で対角線が2つだから2通り、残りのマスの塗り方が2通りであるから、3×2×2＝12通り。これに3色から2色を選んだ場合の組み合わせ3を掛けて3×2＝6を加えの場合を加え、18通り。

問3.

4色の場合は4マスの順列であるから4！＝24通り。これに3色と2色を選ぶ場合の組み合わせ6×2＝12と4×12＝48加え、84通り。

問4.

5色の場合は、4,3及び2色の選び方をこれまでの解答に掛ければよい。

�@ 2色　　5C2×2＝20

�A 3色　　5C3×12＝120

�B 4色　　5C4×24＝120

これらを加え、260通りが求めるもの。

問5.

問4.と同様にやれば良く、

�@2色　　ｎC2×2＝ｎ(ｎ-1)

�A3色　　ｎC3×12＝2ｎ(ｎ-1) (ｎ-2)

�B4色　　ｎC4×24＝ｎ(ｎ-1) (ｎ-2) (ｎ-3)

　　これらを加え、ｎ(ｎ-1)(ｎ2-3ｎ+3)通りが求めるもの。　

NO7「ice」 11/13 20時40分受信 更新11/25