平成１７年６月１１日

[流れ星]

　　　　　第１５５回数学的な応募問題解答

　　　　　　＜解答募集期間：５月７日〜６月１２日

［不思議な戦い方］

皆さん、セ・パ交流試合を始めた今年のプロ野球はどう感じられますか。ジャイアンツファンの太郎さんは、ちっともおもしろくありません。こんな戦い方をしたらどうでしょうか。連続するどの３連戦の中にも勝ち○と負け●を少なくとも１試合作る戦い方です。
　すなわち、３連勝はないが、３連敗もしない戦い方です。

ここで、ｎ試合行った結果、この不思議な戦い方で勝敗の起こる方法は何通りあるか考えてみます。
１試合経過のときは、○か●の２通りです。２試合経過のときは、○○か○●か●○か●●の４通りです。

問題１：３試合経過のときは何通りあるか。

問題２：４試合経過のときは何通りあるか。

問題３：ｎ試合経過のときは何通りあるか。

補題：この数列は一般にどのような規則性がありますか。

ＮＯ１「H7K」　　 5/07: 13時22分受信 更新6/11

前回の問題のときは体調をくずしてました． 第155回の解答を送ります：
1. OOO, XXX以外なので6通り
2. 16-(OOO?,XXX?)-(?OOO,?XXX)+(OOOO,XXXX)=10通り．
3. 求める数をD(n)とする．条件に合うようにn-1試合したとき，最後の2試合について場合わけ．
   a. OO, XXのとき：n試合目はそれぞれX, O
   b. OX, XOのとき：n試合目はどちらでも良い
でなければならない．
ところで，a.となるのは，n-3試合の戦い方と同数で，D(n-3)通り，
よってb.となるのは，D(n-1)-D(n-3)通りであるから，
D(n)=2D(n-1)-D(n-3).
ところで，フィボナッチの漸化式を考えると
f_n=f_(n-1)+f_(n-2)=2f_(n-1)-f(n-3) となり，D(n)の漸化式と等しい．
また，f_n=1,1,2,3,5,...とD(n)/2=1,2,3,5,...とから考えると D(n)=2f_{n+1).

ＮＯ２「cbc」　　 5/08: 00時18分受信 更新6/11

第155回の解答です。今回も面白い問題でした。 漸化式の利用で意外と簡単に処理できました。

問い３と補題の位置関係が気になりました。逆のほうがよかったかも知れません。

＜コメント：154回の解答の修正分と合わせて送信します。（手順6の証明で少し不足していました＾＾；）＞

ＮＯ３「kashiwagi」5/10: 07時37分受信 更新6/11

昨夜何気なくページをめくり、新しい問題が提示されて いることに気づきました。実は前回の掲示で次回は５月１７日と掲示されておりましたのでずっとめくらずにおりました。
早速考えて見ましたが、うーんー、又々驚きました。 本当にフィボナッチの関係は奥が深いですね。こんなところにまで現れるとは、正に目 から鱗でした。

　155回解答

　題意より以下の様に分けられる。

　１試合経過時：２通り

　○、×

　２試合経過時：４通り

　○○、○×、×○、××

　３試合経過時：６通り

　○○×、○×○、○××、×○○、×○×、××○

　４試合経過時：1０通り

　○○×○、○○××、○×○○、○×○×、○××○、×○○×、×○×○、×○××、××○○、××○×

　５試合経過時：１６通り

　○○×○○、○○×○×、○○××○、○×○○×、○×○×○、○×○××、○××○○、○××○×、×○○×○、×○○××、×○×○○、×○×○×、×○××○、××○○×、××○×○、××○××

　即ち、２＋４＝６、４＋６＝１０、６＋１０＝１６となっていることが分かる。即ちフィボナッチ数列である。これらより求めるものは、

問題１．

　６通り

問題２．

　１０通り

問題３．

　ｎ試合経過後の組み合わせをｆ（ｎ） とすると上記よりｆ（ｎ）＝ ｆ（ｎ-１）＋ ｆ（ｎ-2）となる。

補題．

　フイボナッチ数列が成り立つ。

今、ｎ＋２　試合経過後のｆ組み合わせをｆ（ｎ+２） とすると（ｎ＋２） ＝ ｆ（ｎ＋１）＋ ｆ（ｎ）　式のｎに１を代入するとｆ（１）＝2、ｆ（２）＝4であるのでｆ（２）＋ ｆ（１）＝6である。又、問題２の結果より　ｆ（３）＝6であるので確かにｆ（２）＋ ｆ（１）＝　ｆ（３）が成り立つ。

　　　ここでｎ＝Kの時上記式が成り立つとすると、ｆ（ｋ＋２） ＝ ｆ（ｋ＋１）＋ ｆ（ｋ）である。

　　　今、この式の右辺にｆ（ｋ＋１）を加えると、右辺はｆ（ｋ＋１）＋ ｆ（ｋ）＋ｆ（ｋ＋１）となり、ｆ（ｋ＋１）＋ ｆ（ｋ）＝ｆ（ｋ＋２）　であるので結局　ｆ（ｋ＋２） ＋ ｆ（ｋ＋１）となる。　これはｆ（ｋ＋２） ＝ ｆ（ｋ＋１）＋ ｆ（ｋ）の関係からｆ（ｋ＋３） である。

　　　因ってｆ（ｋ＋３） ＝ ｆ（ｋ＋２）＋ ｆ（ｋ＋１）が成立する。この式は以下の様に書ける。

　　　ｆ（（ｋ＋１）＋２） ＝ ｆ（（ｋ＋１）＋１）＋ ｆ（ｋ＋１）

　　　即ち、ｎ＝K＋１でも成立することが分かる。以上よりｆ（ｎ＋２） ＝ ｆ（ｎ＋１）＋ ｆ（ｎ）であることが証明された。

ＮＯ４「Toru」 5/10: 13時59分受信 更新6/11

　第１５５回解答を送ります。　ペンネーム　Toru

３連勝、３連敗はないので、最後尾の、(勝ち)or(負け)の続く数が、２つの場合と１つの場合に分けて考える。

問題１　１試合経過のものに１試合目と逆のものを２つつけたもの
○●●　●○○　　
　　　　２試合経過のものに２試合目と逆のものを１つつけたもの
○○●　○●○　●○●　●●○　
　で計　２＋４＝６通り

問題２　２試合経過のものに２試合目と逆のものを２つつけたもの
○○●● ○●○○ ●○●● ●●○○
　　　　３試合経過のものに３試合目と逆のものを１つつけたもの
○●●○ ●○○●　○○●○　○●○●　●○●○ ●●○●　　で計　４＋６＝１０通り

問題３　n試合経過の時の場合の数をAnとして
　問題１、２と同様に、（n-2試合経過のものにn-2試合目と逆のもの２つつけたもの）と（n-1試合経過のものにn-1試合目と逆のもの１つつけたもの）の和と考えれば、
An=An-1+An-2 (n=3,4,5-----)  A1=2,  A2=4
これはフィボナッチ数列の各項を２倍したものになっています。ということで一般解はβ=(1+√5)/2,α=(1-√5)/2として
　An=2(β^(n+1)-α^(n+1))/(β-α)

蛇足）同じように考えれば、４連勝も４連敗もない場合は　　Bn=Bn-1+Bn-2+Bn-3 などとなりますね

＜水の流れ：私の同じ考えを持っています＞

ＮＯ５「kasama」　5/16　15時03分受信　更新6/11

本題の［不思議な戦い方］についてです。ゲームのツリーを描いて場合数を上げました。n試合後の一般化は２つの連続した勝敗順序の遷移から漸化式を
導出して、一般化しました。当初、遷移(グラフ)を行列で表現して対角化して・・・とやろうとしたのですが、計算が複雑だったので、上記の方法になりました。

問題１、２】
試合経過をツリーで表現すると数え上げ易いです。
　
よって、
　3試合経過=6通り、4試合経過=10通り
です。

【問題３】
2つの連続した勝敗(○,●)の順序を
　A₁:○→○、A₂:○→●、A₃:●→○、 A₄:●→●
とし、上のツリーを参考にして、それらの順序の遷移を考えます。例えば、次のようなグラフで表現するとわかり易いです。
　
n試合経過後の順序A_i(i=1〜4)の場合数をS_n,i、それらの和をS_n(=S_n,1+S_n,2+S_n,3+S_n,4)をとすると、
　S_n+2,1 = S_n+1,3
　S_n+2,2 = S_n+1,1+S_n+1,3
　S_n+2,3 = S_n+1,2+S_n+1,4
　S_n+2,4 = S_n+1,2
ですが、各式の和をとって、
　S_n+2,1+S_n+2,2+S_n+2,3+S_n+2,4 = (S_n+1,1+S_n+1,2+S_n+1,3+S_n+1,4) + (S_n+1,2+S_n+1,3)
　⇒S_n+2 = S_n+1 + (S_n+1,2+S_n+1,3)
です。ここで、
　S_n+1,2 = S_n,1+S_n,3
　S_n+1,3 = S_n,2+S_n,4
ですから、
　S_n+2 = S_n+1 + (S_n,1+S_n,3)+(S_n,2+S_n,4) = S_n+1 + (S_n,1+S_n,2+S_n,3+S_n,4)
　⇒S_n+2 = S_n+1 + S_n
が得られます。この差分方程式の解は、次の補助方程式を解いて、
　λ²-λ-1=0⇒λ=(1±√5)/2
となり、一般項は
　S_n=C₁{(1+√5)/2}ⁿ+C₂{(1-√5)/2}ⁿ
ここで、初期条件S₁=2,S₂=4をあてはめると、c₁=1+√5/5,c₂=1-√5/5となるので、n試合経過の場合数は、
　S_n={(1+√5)/5}･{(1+√5)/2}ⁿ+{(1-√5)/5}･{(1-√5)/2}ⁿ
です。

【補題】
　フィボナッチ数列と同じように、第n+2項が第n+1項と第n項の和になっているとこでしょうか。

＜水の流れ：そうです。この関係を発見してもらいたっかたのです＞

ＮＯ６「uchinyan」5/24　11時32分受信　更新6/11　

＜少し修正及び追加です。＞

第１５５回数学的な応募問題の解答

問題１：6通り。
問題２：10通り。
問題３＆補題：
漸化式を考えます。○を a、●を b で表すことにします。
n 試合目における、n-2 試合目、n-1 試合目の状況を x, y とし、
その場合の場合の数を xy(n) と書き、n 試合目の場合の数を
f(n) と書くことにします。すると、a, b の出現の対称性も考慮して、
n >= 5 に対して、
f(n) = 2 * (aa(n) + ab(n))
aa(n) = bb(n) = ab(n-1) = ba(n-1)
ab(n) = aa(n-1) + ba(n-1) = aa(n-1) + ab(n-1)
これらから、f に関する漸化式を求めると、　　f(n) = f(n-1) + f(n-2)
これは、n >= 5 について考えましたが、問題１及び２より、
n >= 3 で成立します。また、　f(1) = 2, f(2) = 4
これらを解けばいいです。これは、普通の定数係数の3項漸化式で、
結果は、
f(n) = (5 + sqrt(5))/5 * {1/2 * (1 + sqrt(5))}^n
　　　+ (5 - sqrt(5))/5 * {1/2 * (1 - sqrt(5))}^n
なお、漸化式はフィボナッチ数列と同じですが、初項が異なるので、フィボナッチ数列の変種といったところでしょうか。こんな所にも現れるとは (^^;
問題３＆補題の補足：
漸化式の導き方として、こんなのもありますね。　記号は、「問題３＆補題」と同じものを用います。
aaa, bbb がダメですが、n 試合目でこうなる場合の数を g(n) とします。
n >= 5 とします。
f(n) は、f(n-1) に a 又は b を追加した場合からダメな場合 g(n) を引けばいいので、
f(n) = 2 * f(n-1) - g(n)
g(n) は、n-1 試合後で ...baa 又は ...abb となっている場合に等しく、　これは、n-2 試合後で ...ba 又は ...ab となっている場合なので、
n-2 試合後で ...aa 又は ...bb の場合、すなわち、g(n-1) を　f(n-1) から引いた後、n-1 試合後で ...bab 又は ...aba を除くために半分にすればいいので、
g(n) = 1/2 * (f(n-1) - g(n-1))
これらから、f(n) の漸化式は、f(n) = f(n-1) + f(n-2)になります。

Ｎｏ７「uchinyan」5/27　11時11分受信　更新6/11　

　　やはり少し計算が違っていました。
「問題３＆補題の補足その２：」は、以下で置き換えてください。

問題３＆補題の補足その２：
補足で示した漸化式　　f(n) = 2 * f(n-1) - g(n)
の g(n) ですが、次のように考えると、f(n-3) に等しいですね。
要は、n 試合目で ...aaa 又は ...bbb となる場合の数が g(n) ですが、
n-3 試合目が b である場合に n-3 試合以降に a だけが続いた場合、
又はn-3 試合目が a である場合に n-3 試合以降に b だけが続いた場合に等しいです。したがって、g(n) = f(n-3) になります。すると、
f(n) = 2 * f(n-1) - f(n-3)　です。ところで、これは、
f(n) = f(n-1) + f(n-1) - f(n-3)
f(n) = f(n-1) + 2 * f(n-2) - f(n-4) - f(n-3)
f(n) - f(n-1) - f(n-2) = f(n-2) - f(n-3) - f(n-4)
なので、n = 1, 2, 3, 4 の実際の値から、n >= 3 に対して、
f(n) - f(n-1) - f(n-2) = 0
f(n) = f(n-1) + f(n-2)　になります。これは、当然ですが、以前の結果と同じです。
なお、この新しい漸化式は、一般化が容易です。
まず、連勝又は連敗が k 試合, k >= 1, まで許される場合、場合の数を f(n,k) と書くことにすると、同様に考えて、
f(n,k) = 2 * f(n-1,k) - f(n-k-1,k)
f(i,k) = 2^i, 1 <= i <= k, f(k+1,k) = 2^(k+1) - 2
これから、同様の計算をして
f(n,k) = f(n-1,k) + f(n-1,k) - f(n-k-1,k)
f(n,k) = f(n-1,k) + 2 * f(n-2,k) - f(n-k-2,k) - f(n-k-1,k)
f(n,k) = f(n-1,k) + f(n-2,k) + f(n-2,k) - f(n-k-1,k) - f(n-k-2,k)
f(n,k) = f(n-1,k) + f(n-2,k) + f(n-3,k) + ,,, + f(n-k,k)
 + f(n-2,k) - f(n-3,k) - ,,, - f(n-k,k) - f(n-k-1,k) - f(n-k-2,k)
f(n,k) - f(n-1,k) - f(n-2,k) - f(n-3,k) - ,,, - f(n-k,k)
= f(n-2,k) - f(n-3,k) - ,,, - f(n-k,k) - f(n-k-1,k) - f(n-k-2,k)
より、
f(n,k) = f(n-1,k) + f(n-2,k) + f(n-3,k) + ,,, + f(n-k,k)
これは、原理的には、k 次の特性方程式(固有方程式)の解によって表現可能ですが、難しそうなので、省略します。
次に、一回の試合の結果が、勝ち又は負けの二つではなく、
一般に m 個ある場合を考えます。ただし、連続するのは二回までとします。　この場合の場合の数を f(n,2,m) と書くと、これも容易に、
f(n,2,m) = m * f(n-1,2,m) - f(n-3,2.m)
f(1) = m, f(2) = m^2, f(3) = m^3 – m　と分かります。
この場合の特性方程式は、
x^3 - m * x^2 + 1 = 0
この解は、グラフなどで調べると分かりますが、m >= 2 では、
必ず、三つの異なる実数解をもちます。なお、後で使いますが、
m = 2 では、整数解 1 がありますが、それ以外はすべて無理数です。
これを p, q, r とすると、
f(n,2,m) = A * p^(n-1) + B * q^(n-1) + C * r^(n-1)
と書けて、(計算が正しければ (^^;)
A = m * {- qr + m * (q + r) - m^2 + 1}/(p-q)(r-p)
B = m * {- rp + m * (r + p) - m^2 + 1}/(p-q)(q-r)
C = m * {- pq + m * (p + q) - m^2 + 1}/(q-r)(r-p)
となります。特に、m = 2 の場合、今回の問題の場合、特性方程式は、
x^3 - 2 * x^2 + 1 = 0
(x - 1) * (x^2 - x - 1) = 0　ですが、r = 1 とすると、p, q は x^2 - x - 1 = 0 の解で、　C = 0　となり、
f(n,2,2) = A * p^(n-1) + B * q^(n-1)
です。これは、明らかに、今回の場合の漸化式
f(n,2,2) = f(n-1,2,2) + f(n-3,2.2)
の解に一致します。
m = 2 以外は、例えば、F(x) = (x^3 - m * x^2 + 1)/(x-r) として
C = (p-q) * m * (-1) * (F(m) - 1)
なので、r は無理数、m は正の整数ということより、　F(m) が 1 になることはなく、A, B についても同様なので、
A, B, C はいずれも 0 にならず、3項とも出現します。そう考えると、今回の問題は、特殊な場合になっています。
後、一般の f(n,k,m) について考えることも可能ですが、　難しそうなので、省略します

Ｎｏ８　「中川幸一」6/12: 18時01分受信 更新6/18