|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは，算チャレとしては標準的かなぁ。こんな感じで。 (解法1) 1 〜 n のカードと n 個の箱の場合を a(n) 通りとします。 n のカードは n-1 又は n の箱に入れることだけができます。 n の箱に入れたときには，残りが 1 〜 n-1 のカードと n-1 個の箱なので a(n-1) 通り，で， n-1 の箱に入れたときには，n の箱には n-1 しか入らないので，残りが 1 〜 n-2 のカードと n-2 個の箱になって a(n-2) 通り，です。 つまり，a(n) = a(n-1) + a(n-2) になります。ただし，a(2) = 2，a(1) = 1，です。 求めるのは a(14) なので， a(1) = 1，a(2) = 2，a(3) = 3，a(4) = 5，a(5) = 8，a(6) = 13，a(7) = 21，a(8) = 34，a(9) = 55，a(10) = 89， a(11) = 144，a(12) = 233，a(13) = 377，a(14) = 610 そこで，610 通り，になります。 (解法2) 例えば，8 のカードを考えます。このカードは 7，8，9 の箱にだけ入れることができます。 8 のカードが 8 の箱に入った場合は，問題ありません。 8 のカードが 7 の箱に入った場合は，8 の箱には 7 か 9 のカードが入りますが， もし 8 の箱に 9 のカードが入ったとすると， 7 のカードは 6 の箱に，6 のカードは 5 の箱に，．．．2 のカードは 1 の箱に，入るしかなく，1 のカードの入る箱がありません。 そこで，8 の箱には 7 のカードが入るしかありえません。 8 のカードが 9 の箱に入った場合も同様で，8 の箱には 9 のカードが入るしかありえません。 他のカードでも同様なので，結局，カードは同じ番号の箱に入るか，隣同士の番号とクロスして入るか，のいずれかになります。 そこで，場合の数は，番号が同じとクロスとを並べる場合の数に等しくなります。 全体でカードは 14 枚なので，番号が (同じ，クロス) の回数は， (14,0)，(12,1)，(10,2)，(8,3)，(6,4)，(4,5)，(2,6)，(0,7) これより，求める場合の数は，それぞれを並べる場合の数の和になって， 14C0 + 13C1 + 12C2 + 11C3 + 10C4 + 9C5 + 8C6 + 7C7 = 1 + 13 + 66 + 165 + 210 + 126 + 28 + 1 = 610 通り になります。 |
|
ネコの住む家
10月6日（木） 11:05:58
MAIL:uchi@sco.bekkoame.ne.jp 38438 |