平成２３年９月４日
[流れ星]
第２６２回数学的な応募問題解答
＜解答募集期間：8月14日〜9月4日
［球団の勝敗］
今年のプロ野球は勝敗に異変があるようです。主な要因は低反発力にしたボールや東日本大震災により節電のため延長戦は3時間30分を超えた場合は新しいイニングに入らないなどがあります。そこで、ある球団が1ヶ月２０試合を行ったところ、次のことが分かりました。ただし、引き分けはありません。
１．３連勝が一度もない。
２．２連敗も一度もない。
このような現象のとき、20試合の勝敗の起こりうるすべての場合は何通りあるか考えてください。ちなみに最初の３試合は（○、○、×）（○、×、○）（×、○、○）（×、○、×）の４通りです。○は勝ち、×は負けの記号としてある。
NO1「uchinyan」 08/14 15時10分受信 更新9/4
二つの方法で解いてみました。
(解法1)
n 試合の場合の，
n-1
試合目が○で n 試合目が○の場合を a(n) 通り，
n-1
試合目が×で n 試合目が○の場合を b(n) 通り，
n 試合目が×の場合を c(n) 通り，
とすると，
a(n+1)
= b(n)，b(n+1)
= c(n)，c(n+1) = a(n) + b(n)，
a(1)
= 0，b(1)
= 1，c(1) = 1
と書けます。求めるのは s(n) = a(n) + b(n) + c(n) なので，
s(n+1)
= a(n+1) + b(n+1) + c(n+1) = b(n) + c(n) + a(n) + b(n) = s(n) + c(n-1)
=
s(n) + a(n-2) + b(n-2) = s(n) + s(n-2) - c(n-2)
つまり，
s(n+1)
= s(n) + c(n-1)
s(n+1)
= s(n) + s(n-2) - c(n-2)
ですが，
s(n)
= s(n-1) + c(n-2)
s(n+1)
= s(n) + s(n-2) - c(n-2)
なので，
s(n+1)
+ s(n) = s(n) + s(n-1) + s(n-2)
s(n+1)
= s(n-1) + s(n-2)
s(n)
= s(n-2) + s(n-3)
になります。ただし，s(1) = 2，s(2) = 3，s(3)
= 4 です。
そこで，この問題では n = 20 なので，
s(4)
= 5，s(5)
= 7，s(6) = 9，s(7) = 12，s(8) = 16，s(9) = 21，s(10)
= 28，
s(11)
= 37，s(12)
= 49，s(13) = 65，s(14) = 86，s(15) = 114，
s(16)
= 151，s(17)
= 200，s(18) = 265，s(19) = 351，s(20) = 465
となって，465 通り，です。
(解法2)
○，×の並びと考えると，×は並べないので×と×の間に○を 1 個又は 2 個入れればいいです。
これは，まず，○，×を交互に並べておいて，このうちの○の何個かを○○に置き換える，
と考えれば実現できます。このときの置き換えの場合の数は次のようになります。
全体を n 個，○○が p 個とすると，置き換える前の○，×の交互の並びは n-p 個ですが，
この○，×の交互の並びの中に，
n-p
が偶数ならば，
並びの最初が○のとき，○が (n-p)/2 個あり，((n-p)/2)Cp 通り，
並びの最初が×のとき，○が (n-p)/2 個あり，((n-p)/2)Cp 通り，
合計，((n-p)/2)Cp + ((n-p)/2)Cp 通り。
n-p
が奇数ならば，
並びの最初が○のとき，○が (n-p+1)/2 個あり，((n-p+1)/2)Cp 通り，
並びの最初が×のとき，○が (n-p-1)/2 個あり，((n-p-1)/2)Cp 通り，
合計，((n-p+1)/2)Cp + ((n-p-1)/2)Cp 通り。
そこで，求める場合の数を f(n) 通りとし，便宜上，n < k で nCk = 0 としておくと，
f(n)
= Σ(0 <= p <= [(n+1)/3]){g(n,p)}
g(n,p) = ((n-p)/2)Cp + ((n-p)/2)Cp，n-p が偶数，((n-p+1)/2)Cp + ((n-p-1)/2)Cp，n-p が奇数
今の場合は，n = 20 なので，
f(20)
=
(10C0 + 10C0) + (10C1 + 9C1) + (9C2 + 9C2) + (9C3 + 8C3)
+
(8C4 + 8C4) + (8C5 + 7C5) + (7C6 + 7C6) + (7C7 + 6C7)
=
(1 + 1) + (10 + 9) + (36 + 36) + (84 + 56) + (70 + 70) + (56 + 21) + (7 + 7) +
(1 + 0)
= 2
+ 19 + 72 + 140 + 140 + 77 + 14 + 1
=
465
となって，465 通り，です。
(考察＋感想)
(解法1)で得られた漸化式を一般的に解くのは，三次方程式を解くことになり，
不可能ではないですがあまり簡単ではなく，またこの問題では意味はなさそうなのでやめました。
(解法2)のΣで書いた式がその解になっているはずですが，
こちらも，規則性は見えそれなりにきれいな式ですが，簡単な式に書き下すのは難しそうです。
その意味では，もう一工夫できればいいのですが．．．
NO2「ｽﾓｰｸﾏﾝ」 08/15 18時11分受信
「ｽﾓｰｸﾏﾝ」 08/26 19時52分受信
「ｽﾓｰｸﾏﾝ（友人アーベルトのもの）」 08/26 19時52分受信 更新9/4
問題の例にある4つのパターンを
（○、○、×） a
（○、×、○） b
（×、○、○） c
（×、○、×） d とする
20項中のどの連続する3つの項もこの内のいずれかである。
a,b,c,d の繋がりの中で、可能性があるのを拾いだせばよい
aの次はa,b bの次はb,c,d cの次はc,d dの次はa,b である
(a,b,c,d) の漸化式のように考えると
n=1 のとき(a,b,c,d)=(1,1,1,1,) 和は4
n=2 (2,3,2,2) 和は9
n=3 (4,7,5,5) 和は21
n=4 (9,16,12,12) 和は49
n=5 (21,37,28,28) 和は114
n=6 (49,86,65,65) 和は265
ここで、3項ずつだから3*6=18 項の状態である
aの後2項は○○、○× の2とおり
b ○×、×○ の2とおり
c ×○ の1とおり
d ○○、○× の2とおり
よって49*2+86*2+65*1+65*2=465 通り
NO3「浜田明巳」 08/24 17時33分受信
更新9/4
エクセルのマクロで解きました．465通りあります．
Option Explicit
Dim a(20) As Integer 'a(j)=1:win, a(j)=2:lose
Sub Macro1()
Sheets("Sheet1").Select
Cells(1, 1).Value = 0
Call saiki(1)
Range("A1").Select
End Sub
Sub saiki(ByVal n As
Integer)
Dim max As Integer
Select Case n
Case 1
a(1) = 1
max = 2
Case 2
If a(1) = 2 Then
a(2) = 1
max = 1
Else
a(2) = 1
max = 2
End If
Case Else
If a(n - 2) = 1 And a(n - 1) = 1
Then
a(n) = 2
max = 2
ElseIf a(n
- 1) = 2 Then
a(n) = 1
max = 1
Else
a(n) = 1
max = 2
End If
End Select
While a(n) <= max
If n < 20 Then
Call saiki(n
+ 1)
Else
Call hyouji(1)
End If
a(n) = a(n) + 1
Wend
End Sub
Sub hyouji(ByVal x As
Integer)
Dim j As Integer
Cells(1, 1).Value = Cells(1, 1).Value + 1
For j = 1 To 20
Cells(Cells(1, 1).Value, j + 1).Value = shouhai(a(j))
Next j
Range("B" & Cells(1, 1).Value).Select
End Sub
Private Function shouhai(ByVal
n As Integer) As String
If n = 1 Then
shouhai =
"○"
Else
shouhai =
"×"
End If
End Function
＜水の流れ：エクセルで４６５通りのがありましたが、割愛させてもらいます。＞
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。
