|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは比較的よく見る問題で，算チャレでも類題は多く出題されているでしょう。こんな感じで。 (解法1) 成功を○，失敗を×，と表すことにします。 すると，最後の 3 回は○○○，4 回以上投げるときはその前が×，で，それ以外は○○○がない，という並びになります。 そこで，それ以外の部分は○と×で書けるすべての並びから○○○を含む並びを除きます。 ただし，8 回を過ぎると，4 回以上○が続く場合があるので○の個数で場合分けをして数えて除きます。 これを 10 回まで調べて合計すればいいです。 03 回：1 通り。 04 回：1 通り。 05 回：2^1 = 2 通り。 06 回：2^2 = 4 通り。 07 回：2^3 - 1 = 7 通り。 08 回：2^4 - (1 + (1 + 1)) = 16 - (1 + 2) = 16 - 3 = 13 通り。 09 回：2^5 - (1 + (1 + 1) + (2 + 1 + 2)) = 32 - (1 + 2 + 5) = 32 - 8 = 24 通り。 10 回：2^6 - (1 + (1 + 1) + (2 + 1 + 2) + (4 + 2 + 2 + 4)) = 64 - (1 + 2 + 5 + 12) = 64 - 20 = 44 通り。 これですべてなので，合計して， 1 + 1 + 2 + 4 + 7 + 13 + 24 + 44 = 96 通り になります。 (解法2) 最後の 3 回は○○○，4 回以上投げるときはその前が×，で，それ以外は○○○がない，という並び，までは(解法1)と同じ。 そこで，3 回の 1 通り，4 回の 1 通り以降の場合で最後の 4 回を除いた並びを考えます。 一般に，この並びの n 回，全体は n+4 回，の場合を T(n) 通りとします。 すると，T(1) = 2，T(2) = 4，T(3) = 7，で，n >= 4 の場合は， n 回目が×のときは T(n-1) 通り， n 回目が○で n-1 回目が×のときは T(n-2) 通り， n 回目が○で n-1 回目が○のときは n-2 回目が×でなければならないので T(n-2) 通り， そこで，T(n) = T(n-1) + T(n-2) + T(n-3)，になります。 求めるのは全体で 10 回までなので，10 - 4 = 6 より，T(4) = 13，T(5) = 24，T(6) = 44，で， 1 + 1 + T(1) + T(2) + T(3) + T(4) + T(5) + T(6) = 1 + 1 + 2 + 4 + 7 + 13 + 24 + 44 = 96 通り になります。 (解法3) 最後の 3 回は○○○，4 回以上投げるときはその前が×，で，それ以外は○○○がない，という並び，までは(解法1)と同じ。 ここで，最後から数えて n 回の場合を A(n) 通りとすると，A(3) = 1，A(4) = 1，A(5) = 2，A(6) = 4，で， n-1 回の場合から一つ前，後ろからなので n 回，を考えると，○と×の 2 通りあるので A(n-1) * 2 通りですが， ○○○×…n-4 回の並び… の A(n-4) 通りは除かなければならないので， A(n) = A(n-1) * 2 - A(n-4)，です。 求めるのは A(3) 〜 A(10) なので，A(7) = 7，A(8) = 13，A(9) = 24，A(10) = 44，より， A(3) + A(4) + A(5) + A(6) + A(7) + A(8) + A(9) + A(10) = 1 + 1 + 2 + 4 + 7 + 13 + 24 + 44 = 96 通り になります。 (解法2)の T(n) はフィボナッチの親戚のトリボナッチとして有名ですが， (解法3)の A(n) の漸化式は一見違いますが実はトリボナッチの漸化式と等価ですね。 ちょっとうっかりしておりましたが，今回の問題は 10 回以下を求めるので， (解法2)の T(n) を T(n+4) に置き換えて T(3) 〜 T(n) の和を S(n)， (解法3)の A(3) 〜 A(n) の和を B(n)，とすると， S(n) = S(n-1) + S(n-2) + S(n-3) + 1，S(3) = 1，S(4) = 2，S(5) = 4， B(n) = B(n-1) * 2 - B(n-4)，B(3) = 1，B(4) = 2，B(5) = 4，B(6) = 8， が，(少し説明しづらい感じですが)同じようにして導けます。そこで， S(6) = 8，S(7) = 15，S(8) = 28，S(9) = 52，S(10) = 96， B(7) = 15，B(8) = 28，B(9) = 52，B(10) = 96， とすることもできます。 |
|
ネコの住む家
5月15日（金） 11:45:01
43276 |