|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは，世の中的には決して易しいとは言えないと思いますが，類題も見かけたことがあり，算チャレ的には難しくないのでは。 既に同じ解法が書き込まれているとは思いますが，典型的と思われる解法を幾つか書いておきます。 (解法1) 1 の並びの間に 2 又は 3 を一つずつ挟み込めば題意を満たします。 そこで，まず，1 を並べておいて，1 の並びの両端も含めた隙間に 2 か 3 を一つずつ挟み込む，と考えます。 これを，1 の個数で場合分けして行います。 ・1 が 9 個：明らかに 1 通り。 ・1 が 8 個：両端も含めた 9 箇所の隙間から 1 箇所を選んで 2 か 3 を挟み込むので 9C1 * 2^1 = 18 通り。 ・1 が 7 個：両端も含めた 8 箇所の隙間から 2 箇所を選んで 2 か 3 を挟み込むので 8C2 * 2^2 = 112 通り。 ・1 が 6 個：両端も含めた 7 箇所の隙間から 3 箇所を選んで 2 か 3 を挟み込むので 7C3 * 2^3 = 280 通り。 ・1 が 5 個：両端も含めた 6 箇所の隙間から 4 箇所を選んで 2 か 3 を挟み込むので 6C4 * 2^4 = 240 通り。 ・1 が 4 個：両端も含めた 5 箇所の隙間から 5 箇所を選んで 2 か 3 を挟み込むので 5C5 * 2^5 = 32 通り。 ・1 が 3 個以下：明らかに 0 通り。 以上ですべてなので， 1 + 18 + 112 + 280 + 240 + 32 = 683 通り になります。 (解法2) 逆に，2 又は 3 の並びの間に 1 を一つ以上挟み込めば題意を満たします。 そこで，2 又は 3 を○として，まず，○を並べておいて，両端を除いた○の隙間に 1 を挿入しておきます。 そして，残りの 1 を，その個数分，○の並びの両端も含めた隙間から重複を許して選び，挿入します。 これを，○の個数で場合分けして行います。 ・○が 0 個：明らかに 1 通り。 ・○が 1 個：両端の 2 箇所の隙間から重複を許して 8 箇所を選び 1 を挿入するので 2H8 * 2^1 = 9C8 * 2^1 = 18 通り。 ・○が 2 個：両端を含む 3 箇所の隙間から重複を許して 6 箇所を選び 1 を挿入するので 3H6 * 2^2 = 8C6 * 2^2 = 112 通り。 ・○が 3 個：両端を含む 4 箇所の隙間から重複を許して 4 箇所を選び 1 を挿入するので 4H4 * 2^3 = 7C4 * 2^3 = 280 通り。 ・○が 4 個：両端を含む 5 箇所の隙間から重複を許して 2 箇所を選び 1 を挿入するので 5H2 * 2^3 = 6C2 * 2^4 = 240 通り。 ・○が 5 個：両端を除いた○の隙間に挿入する 1 の個数がちょうど 4 個なので，1 の更なる挿入はなく，1 * 2^5 = 32 通り。 ・○が 6 個以上：明らかに 0 通り。 以上ですべてなので， 1 + 18 + 112 + 280 + 240 + 32 = 683 通り になります。 (解法3) 漸化式による解法です。 n 個，n >= 2，の数字の並びの右端が 1 の場合を a(n) 通り，右端が 2 又は 3 の場合を b(n) 通り，とすると， a(n+1) = a(n) + b(n) b(n+1) = a(n) * 2 a(2) = 3, b(2) = 2 です。そして，求めるのは，a(9) + b(9) です。 a(2) = 3, b(2) = 2 a(3) = 5, b(3) = 6 a(4) = 11, b(4) = 10 a(5) = 21, b(5) = 22 a(6) = 43, b(6) = 42 a(7) = 85, b(7) = 86 a(8) = 171, b(8) = 170 a(9) = 341, b(9) = 342 そこで， a(9) + b(9) = 683 通り になります。 |
|
ネコの住む家
2月11日（木） 11:54:33
MAIL:uchi@sco.bekkoame.ne.jp 35776 |