京大理系数学'05年前期[6]

先頭車両から順に1からnまでの番号のついたn両編成の列車がある。ただし、とする。各車両を赤色、青色、黄色のいずれか1色で塗るとき、隣り合った車輌の少なくとも一方が赤色となるような色の塗り方は何通りか。

解答 赤色に塗られる車両は、1両で次が青か黄のこともあるし、2両続くこともあるし、何両も続くこともあるので、先頭車両から順に色の塗り分け方を、右図のように樹形図に書きながら、場合の数を数えてゆくと破綻します。
人間の本能として、何か仕事を与えられたときにいっぺんに仕事を片付けてしまいたいと思ってしまいがちです。でも、人間には頭脳は一つ手は二つしかありません。限られた道具で大きな仕事をするためには、仕事をいくつかに分割して作業を進める必要があります。

樹形図をよく眺めてみると、同じような繰り返しのパターンがあることに気がつきます。樹形図を書くこと自体は問題を解くのには役立ちませんが、問題解決のアイデアを思いつくためには決して無駄な作業とは言えません。

コンピュータに仕事をさせるとき、プログラムを組んで仕事をさせます。そのときに、プログラムの中に同じような繰り返しがよく出てきます。一々記述していると面倒なので、これを1つのサブルーチンにまとめて、いろいろな場所からこのサブルーチンを呼び出すということをよくやります。樹形図の中から繰り返しパターンを抜き出す作業は、まさに、このサブルーチン化作業のトレーニングを行っているわけです。

右図に繰り返しパターンの一つを抜き出しました。
n両目の色は、赤か青か黄です。n両あるときにn両目が赤になる場合の数を通りとします。n両目が青になる場合の数を通りとすると、n両目が黄になる場合の数も通りです。この問題では青と黄を入れ替えても色の塗り方の数に違いはありません。

n両目が赤のときには、両目は赤でも青でも黄でもかまいません。
n両目が青のときには、両目は赤に限られます。
n両目が黄のときも、両目は赤に限られます。

両目が青になるのは、
n両目が赤のときだけです。両目が青になる場合の数は、n両目が赤の場合の数に等しく通りです。
・・・@
両目が黄になる場合の数を考えても@式になります。
両目が赤になる場合の数は、
n両目が赤のときの場合の数,青のときの場合の数.黄のときの場合の数の和になります。
・・・A

の初項を考えます。問題文ではとなっていますが、右上図を見ると、となることがわかります。

1両だけのときの色の塗り方も考えて、としておくと、連立漸化式@,Aは、のときも成り立ちます。
@,Aをとして考え、を初項とします。


連立漸化式の解き方はいろいろありますが、ここでは、@を使ってを消去することにします。
が出てくるように、A式で
nとします。
@を代入すると、
これで、3項間漸化式 ・・・B ができました。
Bの特性方程式
(3項間漸化式を参照)は、


B
これより、は、公比:等比数列です。初項は、
よって、
・・・C

B

これより、は、公比:2等比数列です。初項は、
よって、
・・・D

D−Cより、


さて、n両あるときの色の塗り分け方の方法の数ですが、n両あるとき、n両目は赤か青か黄のどれかですから、
求める方法の数は、

......[]


   京大理系数学TOP   数学TOP   TOPページに戻る

各問題の著作権は出題大学に属します。
©2005-2022
(有)りるらる
苦学楽学塾 随時入会受付中!
理系大学受験ネット塾苦学楽学塾(ご案内はこちら)ご入会は、
まず、こちらまでメールをお送りください。
 雑誌「大学への数学」出版元