『トランプの色あて』

『トランプの色あて』解答

◆愛知県　Y.M.Ojisan さんからの解答。

【解答】　約３０枚　

正確には　

30+ 5041603854695
123979633237026 = 30.040664774713・・・

【計算方法】

下図に示すように　赤＝黒状態から赤＝黒状態までの一つの経路を考えると、
その間に取るトランプの枚数は赤＝黒である。

また、赤＝黒軸に近づく方は１００％当たり、遠ざかる方は経路の最初の１枚が５０％の確率であたる。

従って、期待値は　
２６＋０．５×赤＝黒軸上にある期待値　である。

即ち　

である。

さらに、簡単になるかもしれないが、１０進ＢＡＳＩＣ有理数モードで直接計算した。

X=0
FOR k=1 TO 26　
LET C1=comb(26,k)
LET C2=comb(52,2*k)
LET X=X+C1^2/C2
NEXT k
PRINTX/2+26
END

◆宮城県　甘泉法師さんからの解答。

トランプの全枚数をN枚とする。
ｎ枚めくった後に赤がｒ枚、黒がｂ枚である確率P(N;n,r,b) は

P(N;n,r,b) =_nC_r (N/2)!/(N/2-r)! * (N/2)!/(N/2-b)! / {N!/(N-n)!}

ここで　n=r+b　　r,b≦N/2

よって題意の戦略を採用した場合の期待値Eは

E= N-1
Σ
n=0
Σ
r,b≦N/2,r+b=n N/2- Min(r,b)
N-n * P(N；n,r,b)

【コメント】

N=52　の場合をコンピュータで求められると思いますがやっていません。

◆北海道　小西さんからの解答。

【解答】

2⁴⁸
3³×7²×17×29×31×37×41×43×47 + 51
2

= 3724430600965475
123979633237026 ≒ 30.04[枚]

【計算方法】

与えられた作戦の特徴は以下の通り。

・トランプがどんな順番で並んでいても、半分の26枚は必ず正解する。
・黒、赤の残り枚数が同じ場合にトランプをめくると1/2の確率で正解する。

X-Y平面上の原点から出発して、めくったカードが黒ならX方向へ+1、
赤ならY方向へ+1進むと考えると次の図のようになる。

トランプが10枚の例
(52枚の場合はX方向、Y方向それぞれ26まで)

青い道を通るとき：正解
赤い道を通るとき：不正解
緑の道を通るとき：1/2の確率で正解

トランプの並び順は原点から座標(26, 26)へ行く経路と1対1に対応している。
また、ある経路における正解枚数の期待値は、26を基準として
その経路がy = xの直線にぶつかる毎に1/2増加する。(原点は含むが座標(26, 26)は含まない)

従って、求める期待値をEとすると、

E = 1
─
2 × (全経路でy = xの直線にぶつかる回数の総和)
経路の総数 + 26

となる。

(全経路でy = xの直線にぶつかる回数の総和) = 25
Σ
i=0 (座標(i, i)を通る経路の数)

= 25
Σ
i=0 _2iC_i × _(52-2i)C_(26-i)

= 26
Σ
i=0 _2iC_i × _(52-2i)C_(26-i) - ₅₂C₂₆ × ₀C₀

= 2⁵² - ₅₂C₂₆　　…　(*)

であるから、

E =
1
2 × 2⁵² - ₅₂C₂₆
₅₂C₂₆ + 26

=
2⁵¹
₅₂C₂₆ + 51
2

=
2⁴⁸
3³×7²×17×29×31×37×41×43×47 + 51
2

=
3724430600965475
123979633237026 ≒ 30.04

【(*)の証明】

準備

_2nC_n =
(2n)!
n!×n!

=
2n(2n - 1)
n×n × (2n - 2)!
(n - 1)!×(n - 1)!

=
(4 - 2
─
n ) × _2(n-1)C_(n-1)

= 4×_2(n-1)C_(n-1) - 2C_(n-1)　　…　(1)

ここでC_nはカタラン数。

C_n = _2nC_n / (n + 1)

また、以下の図において原点から座標(n, n)への経路の総数_2nC_nは、
原点から座標(i, i)を通り、その後y = xの直線にぶつからずに座標(n, n)へ行く経路に分解できるので、

_2nC_n = n-1
Σ
i=0 _2iC_i × 2C_(n-1-i)　　…　(2)

証明

n
Σ
i=0 _2iC_i × _2(n-i)C_(n-i) = 2²ⁿ

を帰納法で証明する。

n = 0のとき、左辺 = 右辺 = 1となって成り立つ。

n = kで成り立つと仮定すると、

k+1
Σ
i=0 _2iC_i × _2(k+1-i)C_(k+1-i) =
k
Σ
i=0 _2iC_i × _2(k+1-i)C_(k+1-i) + _2(k+1)C_(k+1) × ₀C₀

(第1項に(1)を適用、第2項に(2)を適用)

=
k
Σ
i=0 _2iC_i × (4×_2(k-i)C_(k-i) - 2C_(k-i)) + k
Σ
i=0 _2iC_i × 2C_(k-i)

=
4 k
Σ
i=0 _2iC_i × _2(k-i)C_(k-i) - k
Σ
i=0 _2iC_i × 2C_(k-i) + k
Σ
i=0 _2iC_i × 2C_(k-i)

= 4×2^2k

= 2^2(k+1)

となってn = k + 1でも成り立つ。
よって、n ≧ 0のとき

n
Σ
i=0 _2iC_i × _2(n-i)C_(n-i) = 2²ⁿ

が成り立つ。

【コメント】

とりあえずの答がわかった後、式を簡略化するために(*)の証明を考えているうちに、
Y.M.Ojisanさんに先を越されてしまいました(^^;
問題の本質ではありませんが、(*)の証明はもっとスマートにできないでしょうか？
元の問題よりこの証明の方に時間が掛かってしまいました…

◆東京都　ぽこぺんさんからの解答。

【別解】

黒・赤のカードの枚数をそれぞれ N 枚とする（問題は N = 26 の場合である）。このとき求める期待値は
N + 2^2N-1
C(2N, N) - 1
2
となる。ただし，二項係数を C(n, r) で表す。

N = 26 の場合，実際の数値は次のようになる。
26 + 281474976710656
61989816618513 - 1
2 =　30.040664774713895…

【証明】

[1] 問題の定式化

設定は上記の Y.M.Ojisan 氏の解と同じとする。方針はカードをめくり始める前の「赤＝黒」状態から，
すべてをめくり終わったときの「赤＝黒」状態までの経路をすべて数え上げるものとする。

ある経路が横軸と k+1 箇所で交われば，「赤＝黒」状態からカードをめくる場合は k 回あることになる。
ただし，横軸との交点は両端を含めて数えるものとする（以下同様）。
したがって，求める期待値 E(N) は
E(N)　= N
Σ
k=1 （横軸との交点が k+1 個の経路の個数）×（N + 0.5 k）
（経路の総数）　　　　　　(1)
により計算できる。

[2] 経路の数え上げ

区間 [0, 2n] において両端で横軸と交わる経路の総数は，1 つの経路を構成する 2n 個の線分のうち
右上に進む n 個の線分を選ぶ方法の数に等しいから，C(2n, n) となる。
また，そのうちで横軸と k+1 箇所（1≦k≦n）で交わる経路の個数を p(n, k) とする。

このことを用いると，(1) は次の形に書ける。
E(n)　=　N + 1
2 C(2N, N) N
Σ
k=1 k p(N, k) 　　　　　　(2)
また n≧1 のとき，区間 [0, 2n] の範囲で，横軸との交点が両端だけであり，
その間では常に横軸よりも上にあるような部分経路（「正経路」と呼ぶ）を考え，その個数を a(n) とする。

p(n, k) の定義より，区間 [0, 2n] で横軸上に底辺を持つ山または谷の個数は k 個あることになる。
それぞれの山または谷を横軸に関して個別に対称移動したものも同じ条件を満たしているから，
経路の個数 p(n, k) は，正経路の総数を 2^k 倍すれば得られる。

自然数 n を k 個の自然数へ分割するすべての方法の集合を
π　=　{ (t₁, …, t_k) | t_i > 0 (1≦i≦k)， t₁ + … + t_k = n }
と書くと，以上のことから
p(n, k)　=　2^k Σ a(t₁) a(t₂) … a(t_k)
(t₁, …, t_k)∈π
となる。

ここで，a(n) の母関数 f(x) を形式的に
f(x)　= Σ a(n) xⁿ 　　　　　　(3)
n≧1
により定義する。このとき，p(n, k) は
{ 2 f(x) } ^k 　　　　　　(4)
の展開式の xⁿ の係数に等しい。証明は展開して係数を比較すればよいが，ここでは省略する。

[3] 非負経路の個数

n≧1 のとき，区間 [0, 2n] の範囲で，横軸との交点が両端を含む 2 個以上あり，
横軸よりも下にはみ出さない部分経路（「非負経路」と呼ぶ）を考え，その個数を b(n) とする。
また，b(0) = 1 と定義する。（{b(n)} は「Catalan 数列」と呼ばれる）

区間 [0, 2n] の範囲での正経路に対して，その [1, 2n-1] の範囲の部分経路を左に 1，下に 1 だけ平行移動すると，
[0, 2n-2] の範囲での非負経路になるから，
a(n)　=　b(n-1) 　　　　　　(5)
が成立する。

非負経路の個数は，下図のように，各格子点にその左上と左下の数の和を割り当てる方法により求められる。
ただし，最も左の数は常に 1 とし，横軸上の数は左上の数と等しくする。この横軸上に並ぶ数列が b(n) になっている。

ここで，左下から右上に向かう各半直線上に並ぶ数列を考える。左から n 本目（最左を n = 0 とする）の半直線上で，
横軸から r 個目（横軸上を r = 0 とする）の数を B(n, r) と書くことにすると，定義より次の式が成り立つ。
B(0, r)　=   1 （r≧0）
B(n, r)　=   B(n-1, r+1) + B(n, r-1) （n＞0，r＞0 のとき)
B(n-1, r+1) （n＞0，r＝0 のとき）
この B(n, r) は
B(n, r)　=   r+1
n+r+1 C(2n+r, n) 　　　　　　(6)
を満たしている（証明略）。特に r = 0 の Catalan 数列の場合は
b(n)　=　B(n, 0)　=   1
n+1 C(2n, n)
である。この B(n, r) に関しては，等式
Σ B(i, u) B(j, v)　=　B(n, u+v+1) 　　　　　　(7)
i+j=n
が成立する（証明略）。

ここで B(n, r) の母関数を形式的に
g(x, r)　= Σ B(n, r) xⁿ　=　B(0, r) + B(1, r) x + B(2, r) x²+ …
n≧0
と定義すると，(7) で u = 0，v = k とおくことにより，
{ g(x, 0) }^k　=　g(x, k-1) 　　　　　　(8)
が成立することがわかる。

[4] 経路数の計算

以上の準備の元で p(n, k) を求める。 (3)，(5) により，
f(x)　=　x Σ b(n-1) x^n-1　=　x Σ b(n) xⁿ　=　x g(x, 0)
n≧1 n≧0
と書けるから，さらに (8) を用いて
{ 2 f(x) } ^k　=　{ 2x g(x, 0) } ^k　=　2^k x^k g(x, k-1)
となる。したがって，これを展開したときの xⁿ の係数は
2^k B(n-k, k-1)
で与えられる。以上より，
p(n, k)　=   k
n   2^k C(2n-k-1, n-1)
であることがわかり。これを用いれば，
E(n)　=　N + 1
2N C(2N, N)    N
Σ
k=1 k² 2^k C(2N-k-1, N-1)
となる。

ここで，簡単な計算により
N
Σ
k=1 2^kC(2N-k-1, N-1)　=　2^2N-1 　　　　　　(9)

N
Σ
k=1 k 2^kC(2N-k-1, N-1)　=　N C(2N, N) 　　　　　　(10)

N
Σ
k=1 k² 2^kC(2N-k-1, N-1)　=　N (2^2N - C(2N, N)) 　　　　　　(11)
などが成り立つことがわかるので，この (11) を用いて，
E(n)　=　N + 2^2N - C(2N, N)
2 C(2N, N)
となり，これを整理して冒頭の式を得る。 ■

【感想】

途中まで進めているときに，Y.M.Ojisan 氏から解が出されてしまったので少々がっくりしたのですが，
Σ を消した簡単な形の式が出たので投稿することにしました。
正直にすべての経路を数え上げているので回り道かもしれませんが，素直で分かりやすい方法だと思います。
（母関数などを経由せずに，もっと短く証明できるといいのですが。）
長くなるので，途中の (6)，(7)，(9)，(10)，(11) 式の証明は省略しました。別途，この証明は問題として投稿したいと思います。
どれもきれいな形をした式なので，挑戦していただけると幸いです。

◆出題者のコメント。

Y.M. Ojisanさん、甘泉法師さん、小西さん、ぽこぺんさん、素敵な解答をありがとうございました。
改めて、ここのレベルの高さを感じました。
Σを使わない答が出来るとは思ってもいませんでした。
また、この問題から新たな問題も派生して、出題者冥利につきるというものです。
いろいろな解法がでていますが、一応出題者の考えていた式も書いておきたいと思います。

みなさんお気づきのように、この作戦では必ず26枚は当たります。
問題のキーとなるのは残りの枚数が赤黒同じという局面が何回現れるか、ということです。
その時には、1/2の確率で当たります。

P(n,n)を、赤黒ともにn枚ずつ残る確率とすると、求める答は

26 + 26
Σ
n=1 P(n,n)　になります。

P(n,n)はいろいろな求め方がありますが、こんなのはどうでしょう？

P(n,n) = C(26,n)C(26,n)2n!(52-2n)!
52!

分母はトランプ52枚の並び方の総数です。

分子の考え方：まず残っている赤黒それぞれn枚を選びます。
この2n枚は2n!通りの並び方があり、既に出た(52-2n)枚は(52-2n)通りの並び方があります。

P(n,n) = C(26,n)C(26,n)
C(52,2n) と少しすっきりします。

答は30.04になります。

◆東京都　Toshi さんからの解答。

問題を定式化します。

n個の1とn個の-1を無作為に並べ、順にX_i(i=1,…,2n)とする。

確率変数Y_i,Z_i(i=1,…,2n)を次のように決める。

・Y_i= 1 （X_i・(X_i+…+X_2n)>0のとき）,
　Y_i=0（その他の場合）

・Z_i=「確率 1
2 で1、確率 1
2 で0を取る確率変数」（X_i+…+X_2n=0のとき）,
　Z_i=0（その他の場合）

2n
Σ
i=1 (Y_i+Z_i)の期待値を求めよ。

各X_iは1と-1が赤黒どちらかに対応していると考えてください。
Y_iは赤黒の残り枚数が異なる場合、正解すれば1を取る確率変数。
Z_iは赤黒の残り枚数が同じ場合、正解すれば1を取る確率変数。
を意味します。

で、結論は

１．E[Y₁+…+Y_2n]=n

２．E[Z₁+…+Z_2n]= 2²ⁿ-1
2C(2n,n)

となって、ぽこぺんさんの書かれている一般式が出てきます。

それぞれ求めてみます。

１．E[Y₁+…+Y_2n]=n

これは、X_iの並べ方に関わらず
Y₁+…+Y_2n=n
と定数になりますので、期待値も当然nです。

証明は例えば帰納法を使えばできますが、省略します。
概念的にはY.M.Ojisan さんの解からも明らかです。

２．E[Z₁+…+Z_2n]= 2^2n-1
C(2n,n) - 1
2

これは、E[Z₁+…+Z_2n]=E[Z₁]+…+E[Z_n]と考えるとよいです。

和の期待値は独立であるかいなかに関わらず期待値の和に分解できますので、期待値を求める問題では、このように考えたほうが簡単に求まる場合がよくあります。

X_i+…+X_2n=0となる確率は、
iは偶数のときは明らかにゼロですので、i=2j+1 (j=0,…n-1)としますと、
これは、2jまでで1と-1がj個ずつ、(2j+1)～2nまでで1と-1が(n-j)個ずつとなる確率ですから、

Pr(X_2j+1+…+X_2n=0)= C(2j,j)C(2(n-j),n-j)
C(2n,n)

となります。

したがって、Z_2j+1の期待値は、

E[Z_2j+1]= 1
2 ・Pr(X_2j+1+…+X_2n=0)= C(2j,j)C(2(n-j),n-j)
2C(2n,n)

です。もちろん、E[Z_2j]=0です。

よって、

E[Z₁+…+Z_2n]

= n-1
Σ
j=0 C(2j,j)C(2(n-j),n-j)
2C(2n,n)

= 2^2n-1
C(2n,n) - 1
2

が求まります。

n
Σ
j=0 {C(2j,j)C(2(n-j),n-j)}=2²ⁿ

は、小西さんの証明にある通り帰納法でも証明できますが、級数展開

1
√(1-4t) = ∞
Σ
k=0 C(2k,k)t^k

1
1-4t = ∞
Σ
k=0 (4t)^k

から、

∞
Σ
k=0 (4t)^k =( ∞
Σ
k=0 C(2k,k)t^k)( ∞
Σ
j=0 C(2j,j)t^j)

が成り立つので、これのtⁿの係数を比較して証明することもできます。

tⁿの係数は、左辺が4ⁿ、右辺が n
Σ
j=0 {C(2j,j)C(2(n-j),n-j)}ですね。

◆東京都　ぽこぺんさんからの「出題者のコメントに対するコメント」。

上記の出題者のコメントの中にある p(n,n) の形になっていると，総和は簡単に計算することができます。
よく見ると，冒頭の Y.M.Ojisan の解にある式もまったく同じものでした。
当初，分母に k を含む形の総和だったので敬遠してしまいましたが，どうやら， Σ を消した形を求めるには，これが最も簡単な方法のようですね。

n
Σ
k=1 C(n, k)²
C(2n, 2k)   =   n!²
(2n)! n
Σ
k=1 (2k)! (2n-2k)!
k!² (n-k)!²   =   1
C(2n, n) n
Σ
k=1 C(2k, k) C(2n-2k, n-k)

となりますが，ここで総和の範囲の下限を k = 0 に変えると，
n
Σ
k=0 C(2k, k) C(2n-2k, n-k)　=　4ⁿ (※)
が成立することが下記のようにして示せます。これを用いると，
n
Σ
k=1 C(2k, k) C(2n-2k, n-k)　=　4ⁿ - C(2n, n)
すなわち
n
Σ
k=1 C(n, k)²
C(2n, 2k)   =   4ⁿ
C(2n, n)   - 1
が得られます。

(※) の証明は数学的帰納法でもいいですが，母関数を使った方法を下に掲げます。
f(x)　=   1
√(1-4x)   =　(1-4x)^-1/2
とおくと，その k 次導関数は
f^(k)(x) =　(- 1
2 )・…・(- 2k-1
2 ) (-4)^k (1-4x)^-(2k+1)/2　 =   (2k)!
k! (1-4x)^-(2k+1)/2
となるので，Maclaurin の定理によって，
f(x)　=   ∞
Σ
k=0 C(2k, k) x^k
という展開が得られます。
つまり，これが C(2k, k) の母関数であったわけです。

ここで，
{f(x)}²　=   ∞
Σ
n=0
Σ
i+j=n C(2i, i) C(2j, j) xⁿ
と書けますから，
{f(x)}²　=   1
1-4x   =   ∞
Σ
n=0 4ⁿ xⁿ
と比較して， (※) が得られます。

　『トランプの色あて』へ

　数学の部屋へもどる

(全経路でy = xの直線にぶつかる回数の総和)	=	25 Σ i=0	(座標(i, i)を通る経路の数)
	=	25 Σ i=0	_2iC_i × _(52-2i)C_(26-i)
	=	26 Σ i=0	_2iC_i × _(52-2i)C_(26-i) - ₅₂C₂₆ × ₀C₀
	=	2⁵² - ₅₂C₂₆　　…　(*)


26 +	281474976710656 61989816618513	-	1 2	=　30.040664774713895…


E(N)　=	N Σ k=1	（横軸との交点が k+1 個の経路の個数）×（N + 0.5 k）（経路の総数）	(1)


E(n)　=　N +	1 2 C(2N, N)	N Σ k=1	k p(N, k) 　　　　　　(2)


	π　=　{ (t₁, …, t_k) \| t_i > 0 (1≦i≦k)， t₁ + … + t_k = n }


p(n, k)　=　2^k	Σ	a(t₁) a(t₂) … a(t_k)
	(t₁, …, t_k)∈π


B(0, r)　=	1	（r≧0）

B(n, r)　=	B(n-1, r+1) + B(n, r-1)	（n＞0，r＞0 のとき)
	B(n-1, r+1)	（n＞0，r＝0 のとき）


	Σ	B(i, u) B(j, v)　=　B(n, u+v+1) 　　　　　　(7)
	i+j=n


g(x, r)　=	Σ	B(n, r) xⁿ　=　B(0, r) + B(1, r) x + B(2, r) x²+ …
	n≧0


f(x)　=　x	Σ	b(n-1) x^n-1　=　x	Σ	b(n) xⁿ　=　x g(x, 0)
	n≧1		n≧0


	{ 2 f(x) } ^k　=　{ 2x g(x, 0) } ^k　=　2^k x^k g(x, k-1)


	N Σ k=1	2^kC(2N-k-1, N-1)　=　2^2N-1 　　　　　　(9)


	N Σ k=1	k 2^kC(2N-k-1, N-1)　=　N C(2N, N) 　　　　　　(10)


	N Σ k=1	k² 2^kC(2N-k-1, N-1)　=　N (2^2N - C(2N, N)) 　　　　　　(11)


f^(k)(x) =　(-	1 2	)・…・(-	2k-1 2	) (-4)^k (1-4x)^-(2k+1)/2　 =	(2k)! k!	(1-4x)^-(2k+1)/2