アーカイブ一覧へ戻る
京都大学 前期 2005年 解答解説 このページの閲覧数
前の年度 2004年 次の年度 2006年
🧭 2005年度の関連ナビゲーション:
第1問 (問題) 第1問 (解答) 第2問 (問題) 第2問 (解答) 第3問 (問題) 第3問 (解答) 第4問 (問題) 第4問 (解答) 第5問 (問題) 第5問 (解答) 第6問 (問題) 第6問 (解答)

この問題のOpen Issue（0件）

GitHubで確認 ↗

この問題に紐づくOpen Issueはありません。

情報取得：。最新の状態はGitHubで確認できます。

京都大学 前期 2005年 第6問 (解答解説)

📝 問題

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

✏️ 解答解説

【解答】

車両の配置と$k$両目から$k+1$両目への塗り分けの状態遷移

図 1: 車両の配置と両目から両目への塗り分けの状態遷移

左から両目まで塗る時，両目が赤である場合の数を，青か黄色である場合の数をとする．両目を塗る時，これが赤ならば両目は任意，それ以外なら両目は赤で塗らないといけないから

である．また初期条件は

である．(式1),(式2)からを消して

，，

だから，漸化式を解いて

となる．従って の時もとめる場合の数は

である．

この解答の誤りや分かりにくい点に気づきましたか？ GitHubで報告する