東京大学 2001年度
文系数学 第3問

解答

(1)

$d=a-b$ とおく。初めは $d=0$ である。操作の規則から、差 $d$ の変化だけを見れば十分である。 $d=0$、すなわち $a=b$ のとき、表が出れば $A$ だけが1進むので $d=1$ となり、裏が出れば $B$ だけが1進むので $d=-1$ となる。したがって $d=0$ から次に $d=0$ へ進むことはない。 $d=1$、すなわち $A$ が $B$ より1だけ右にあるとき、表なら $A,B$ がともに1進むので $d=1$ のままであり、裏なら $B$ だけが1進むので $d=0$ となる。

同様に $d=-1$ のときは、裏なら $d=-1$ のままで、表なら $d=0$ となる。よって $d\ne 0$ の場合からは、表裏2通りのうちちょうど1通りで $d=0$ に戻る。 $n$ 回後の出方は全部で $2^n$ 通りあり、そのうち $d=0$ であるものが $X_n$ 通りである。したがって $d\ne 0$ であるものは $2^n-X_n$ 通りであり、それぞれから次の1回で $d=0$ になる出方は1通りずつである。ゆえに $X_{n+1}=2^n-X_n$ である。

(2)

$1$ 回後には $d=1$ または $d=-1$ なので $X_1=0$ である。

(1)の漸化式 $X_{n+1}=2^n-X_n$ に対して、$2^n/3$ は特解である。実際、$\frac{2^{n+1}}{3}=2^n-\frac{2^n}{3}$ である。そこで $Y_n=X_n-\frac{2^n}{3}$ とおくと

となる。

また $Y_1=X_1-\frac{2}{3}=-\frac{2}{3}$ であるから $Y_n=\frac{2(-1{)}^n}{3}$ である。したがって $X_n=\frac{2^n+2(-1{)}^n}{3}$ である。

別解。$d=0$ である場合の数を $X_n$、$d\ne 0$ である場合の数を $Y_n$ とおくと、$X_n+Y_n=2^n$ である。次に $d=0$ になるのは、直前に $d\ne 0$ であった各出方から1通りずつなので $X_{n+1}=Y_n$ である。よって直ちに $X_{n+1}=2^n-X_n$ が得られ、同じ漸化式を解けば上の式になる。