大阪大学 2008年度 前期日程 第2次学力試験理系数学 第5問

表を $H$，裏を $T$ と書く。 $n$ 回目で終わるためには，最後の500回，すなわち $n-499,n-498,\dots ,n$ 回目がすべて表でなければならない。また $n>500$ のとき，$n-500$ 回目も表であると，500回連続の表は $n-1$ 回目以前にすでに完成してしまう。したがって $n>500$ では $n-500$ 回目は裏である必要がある。

(1) $501\leqq n\leqq 1000$ とする。このとき $n$ 回目で終わる列は$$\underset{n-501\text{ 回}}{\underbrace{\ast \ast \cdots \ast }}T\underset{500\text{ 回}}{\underbrace{HH\cdots H}}$$の形である。最初の $n-501$ 回は長さが高々499なので，その中に表500回連続は起こり得ない。したがって自由に選べる。

よってそのような列の個数は $2^{n-501}$ 通りであり，全事象は $2^n$ 通りだから $$p(n)={\displaystyle \frac{2^{n-501}}{2^n}}={\displaystyle \frac{1}{2^{501}}}$$ である。これは $n$ によらず一定である。

(2)

まず $n=1001$ のとき，最後の形は$$\underset{500\text{ 回}}{\underbrace{\ast \ast \cdots \ast }}T\underset{500\text{ 回}}{\underbrace{HH\cdots H}}$$である。最初の500回の列のうち，すべて表である1通りだけは，その時点で終了してしまうので許されない。したがって $$p(1001)={\displaystyle \frac{2^{500}-1}{2^{1001}}}$$ である。

次に $n=1002$ のとき，最後の形は$$\underset{501\text{ 回}}{\underbrace{\ast \ast \cdots \ast }}T\underset{500\text{ 回}}{\underbrace{HH\cdots H}}$$である。最初の501回の中に表500回連続が現れてはいけない。長さ501の列で表500回連続を含むものは$$\underset{501\text{ 回}}{\underbrace{HH\cdots H}},\underset{500\text{ 回}}{\underbrace{HH\cdots H}}T,T\underset{500\text{ 回}}{\underbrace{HH\cdots H}}$$の3通りである。よって $$p(1002)={\displaystyle \frac{2^{501}-3}{2^{1002}}}$$ である。

したがって$$\begin{array}{rl}{\displaystyle p(1002)-p(1001)}& {\displaystyle ={\displaystyle \frac{2^{501}-3}{2^{1002}}}-{\displaystyle \frac{2^{500}-1}{2^{1001}}}}\\ {\displaystyle }& {\displaystyle ={\displaystyle \frac{2^{501}-3-2(2^{500}-1)}{2^{1002}}}}\\ {\displaystyle }& {\displaystyle =-{\displaystyle \frac{1}{2^{1002}}}\mathrm{.}}\end{array}$$(3)

長さ $L$ の表裏の列のうち，表が500回続けて現れないものの個数を $A_L$ とする。$n\geqq 501$ では，$n$ 回目で終わる列は $\text{長さ }n-501\text{ の許される列}T{H}^{500}$ の形であるから，$$p(n)={\displaystyle \frac{A_{n-501}}{2^n}}$$ である。 $1002\leqq n\leqq 1500$ とし，$L=n-501$ とおく。このとき $501\leqq L\leqq 999$ である。長さ $L$ の許される列に，次の1回を付け加えて長さ $L+1$ の列を作る。単純には $2A_L$ 通りあるが，最後に表を付け加えたことで新たに末尾に表500連続ができるものを除かなければならない。

そのような列は，長さ $L$ の列の末尾499個がすべて表で，その直前が裏であるものに限られる。なぜなら直前も表なら，長さ $L$ の時点ですでに表500連続ができてしまっているからである。残りの前半部分の長さは $L-500$ であり，$L\leqq 999$ なのでこの前半部分の中に表500連続は起こり得ない。したがって除くべき列は $2^{L-500}$ 通りである。

よって $A_{L+1}=2A_L-2^{L-500}$ である。したがって$$\begin{array}{rl}{\displaystyle p(n+1)-p(n)}& {\displaystyle ={\displaystyle \frac{A_{L+1}}{2^{n+1}}}-{\displaystyle \frac{A_L}{2^n}}}\\ {\displaystyle }& {\displaystyle ={\displaystyle \frac{A_{L+1}-2A_L}{2^{n+1}}}}\\ {\displaystyle }& {\displaystyle =-{\displaystyle \frac{2^{L-500}}{2^{n+1}}}\mathrm{.}}\end{array}$$ここで $L=n-501$ だから$$-{\displaystyle \frac{2^{L-500}}{2^{n+1}}}=-{\displaystyle \frac{2^{n-1001}}{2^{n+1}}}=-{\displaystyle \frac{1}{2^{1002}}}\mathrm{.}$$よって $1002\leqq n\leqq 1500$ で $$p(n+1)-p(n)=-{\displaystyle \frac{1}{2^{1002}}}$$ である。

$n$ 回目で初めて終わる列は
「許される前半」$T{H}^{500}$ と一意に分解できる。