平成２１年９月２０日

[流れ星]

　　　　　第２２９回数学的な応募問題解答

　　　　　　＜解答募集期間：８月２３日〜９月２０日

［開票経過］

皆さん！衆議院総選挙が、8月30日に行われます。そこで、選挙の問題を考えました。

Ａ,Ｂの二人が立候補したある選挙区は大激戦でして、１票ごとの開票経過が気になります。開票経過の起こりうる方法はすべて同じとする。

問題１：Ａ候補者が５票で、Ｂ候補者が３票のとき、一票ごとの起こりうる開票経過は何通りあるか求めよ。

問題２：Ａ候補者が５票で、Ｂ候補者が３票のとき、一票ごとの開票中ずっとＡ候補者の得票がＢ候補者の得票を上回る確率を求めよ。

問題３：Ａ候補者がa票で、Ｂ候補者がｂ票のとき、一票ごとの起こりうる開票経過は何通りあるか求めよ。

問題４：Ａ候補者がa票で、Ｂ候補者がｂ票のとき、一票ごとの開票中ずっとＡ候補者の得票がＢ候補者の得票を上回る確率を求めよ。ただし、ａ＞ｂである。

考察：　Ａ候補者がa票で、Ｂ候補者がｂ票のとき、一票ごとの開票中ずっとＡ候補者の得票がＢ候補者の得票を上回る開票経過は何通りあるか、可能なら考えてください。

ＮＯ１「uchinyan」 8/23 13時29分受信 更新9/20

第２２９回数学的な応募問題
［開票経過］

A の票が 1 票開くのを右に一区画進み，B の票が 1 票開くのを上に一区画進む，と置き換えると，
開票状況は，碁盤状の経路の経路選択と等価になります。
これは，A の票が a 票，B の票が b 票，a > b，の場合には，座標上で (0,0)，(a,0)，(0,b)，(a,b) の長方形で，
この長方形の辺上及び内部の格子点からなる碁盤状の経路になります。
また，横に進むのを A，縦に進むのを B，と書くことにします。

以下では，この置き換えのもとで考えます。

問題１：
(0,0) から (5,3) なので，(5+3)C3 = 8C3 = (8 * 7 * 6)/(3 * 2 * 1) = 56 通り。

問題２：
全体でも高々 56 通りなので，どういう場合が可能か，具体的に調べてみましょう。
すると，次の通りです。
01 : AAAAABBB
02 : AAAABABB
03 : AAAABBAB
04 : AAAABBBA
05 : AAABAABB
06 : AAABABAB
07 : AAABABBA
08 : AAABBAAB
09 : AAABBABA
10 : AABAAABB
11 : AABAABAB
12 : AABAABBA
13 : AABABAAB
14 : AABABABA
うまり，14 通り。
そこで，確率は，14/56 = 1/4 になります。

考察：
開票中に A の得票が B の得票を上回る場合の数を，先ほどの座標上の格子点の経路の考え方を基に，
ここで求めてしまいましょう。

開票中に A の票が常に多いのは，(x,y) として，(0,0) 以外は y < x となる経路です。
つまり，y = x - 1 までは OK で，y = x になったらダメになります。
そして，全体からダメな経路を除けばいいです。

まず明らかに，全体は (a+b)Cb 通りです。

また，これも明らかですが，最初に (0,1) に行く場合はダメです。
これは，その後 (0,1) から (a,b) に向かうので，(a+b-1)C(b-1) 通りです。

次に最初に (1,0) に行く場合ですが，この場合でダメな場合は，
その後何処かで y = x を通るので，最初にこうなった点を P とします。
そして，それ以降は P から (a,b) に向かいます。
今，この後半の経路を y = x で折り返したものを考えると，P から (b,a) に向かいます。
一方で，(1,0) から (b,a) に向かう経路は，1 > 0，b < a なので，必ず，y = x を通ります。
そこで，最初に y = x となる点を Q とし，Q から (b,a) に向かう経路を y = x で折り返すと，
先ほどのダメな経路が得られます。
つまり，この折り返しによって，
最初の (1,0) に行ってダメになる場合と (1,0) から (b,a) への経路の場合とが１：１に対応しています。
そこで，最初に (1,0) に行ってダメになる場合は，(a+b-1)C(b-1) 通りです。

結局，ダメな場合は 2 * (a+b-1)C(b-1) 通りになります。

そこで，開票中に A の票が常に多いのは，全体 (a+b)Cb 通りから引いて，
(a+b)Cb - 2 * (a+b-1)C(b-1)
= (a+b)!/a!b! - (a+b-1)!/a!(b-1)!
= (a+b-1)!/a!b! * ((a+b) - 2b)
= (a+b-1)!/a!b! * (a-b)
= (a-b)/(a+b) * (a+b)!/a!b!
= (a-b)/(a+b) * (a+b)Cb 通り
になります。

問題３：
考察：より，(a+b)Cb 通り。

問題４：
考察：より，((a-b)/(a+b) * (a+b)Cb)/(a+b)Cb = (a-b)/(a+b) になります。

(感想)
考察：が先に解けてしまいました。
開票中に A の得票が B の得票を上回る場合の数は，票数が同数以下の場合のカタラン数に似ているので，
カタラン数を求める場合の考え方を流用して求めてみました。

ＮＯ２「kashiwagi」 9/02 07時39分受信 更新9/20

229回解答

【問題1】

　題意よりAが5個およびBが3個合計8個の並べ方だから　8！/5！3！＝56となる。または、5個のAの間6箇所に重複を許し、3個入れるとも考えられるので、6H3＝8C3＝56となる。

【問題2】

　Aを○Bを×として常にAが上回る場合を書き出すと下に示す14種類である。

○○○○○×××

○○○○×××○

○○○○××○×

○○○○×○××

○○○××○×○

○○○××○○×

○○○×○××○

○○○×○×○×

○○○×○○××

○○×○×○×○

○○×○×○○×

○○×○○××○

○○×○○×○×

○○×○○○××　　因って、求める確率は14/56＝1/4

【問題3】

　問題1より、(a+ｂ)！/a！ｂ！

【問題4】

　問題1でAとBの得票の差は2、そこで差を1、2と変えて、場合の数を求め確率を計算してみる。例えば、3-2、4-3、5-4を試すと。各々1/5、1/7および1/9となる。又、3-1、4-2も行うと、1/2、1/3となる。これらより推定し、求める確率は　a-ｂ/a+ｂである。

【考察】

　問題3と4より（a+ｂ-1）！（a-ｂ）/a！ｂ！が求めるものである。但し狙いは、きちんと理論計算で求めろとの事でしょうが・・・・、色々やったのですが、数が大きくなるとその場合分けが複雑で、断念致しました。

ＮＯ３「nidodukehakusai」9/12 18時10分受信 更新9/20

「問題４」 および 「考察」 に対して解答を書きます。

「問題４」の答えは、(a-b)/(a+b) です。

「考察」の答えは、(a-b)*(a+b-1)!/(a!*b!) 通り です。

この問題は、「Ballot Problem」と呼ばれているものです。
http://webspace.ship.edu/msrenault/ballotproblem/
詳しい証明が、例えば次の本にも載っています。
ADVANCED COMBINATORICS (LOUIS COMTET 著 )

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。