東北大学 2001年度 前期日程理系数学 第3問

カードに書かれた数を $2^{k}m$ と表す。ただし $m$ は奇数である。このとき、偶数である限り2で割って最後に得られる奇数は $m$ である。したがって得点は $m$ である。

得点の総和を、$k$ ごとに分けて求める。 $k=0$ では奇数 $1,3,\dots ,199$ が出るので和は $$1+3+\cdots +199={100}^2=10000$$ である。$k=1$ では $2m\leqq 200$ なので $m\leqq 100$ の奇数の和で $1+3+\cdots +99={50}^2=2500$ である。

同様に続けると、得点総和は $10000+2500+625+169+36+9+4+1$ である。ここで例えば $625={25}^2$、$169={13}^2$ は、それぞれ $m\leqq 50$、$m\leqq 25$ の奇数和である。

したがって得点総和は $13344$ である。カードは全部で200枚だから、期待値は $${\displaystyle \frac{13344}{200}}={\displaystyle \frac{1668}{25}}$$ である。よって ${\displaystyle \frac{1668}{25}}$ である。

1から $N$ までの得点総和を $T(N)$ とする。
奇数カードの寄与と、偶数カードを2で割った後の寄与に分けると
短い再帰式が得られる。

$T(N)$ を、1から $N$ までのカードの得点総和とする。
奇数カードの得点はその数自身であり、偶数 $2m$ の得点は
カード $m$ の得点と同じである。したがって$$T(N)=\sum _{\begin{array}{c}1\leqq j\leqq N\\ j\text{ は奇数}\end{array}}j+T\left(\lfloor {\displaystyle \frac{N}{2}}\rfloor \right)\mathrm{.}$$正の奇数を小さい方から $r$ 個足した和は $r^2$ だから$$\begin{array}{rl}{\displaystyle T(200)}& {\displaystyle ={100}^2+{50}^2+{25}^2+{13}^2}\\ {\displaystyle }& {\displaystyle +6^2+3^2+2^2+1^2}\\ {\displaystyle }& {\displaystyle =13344.}\end{array}$$200枚は等確率なので、期待値は$${\displaystyle \frac{T(200)}{200}}={\displaystyle \frac{13344}{200}}={\displaystyle \frac{1668}{25}}\mathrm{.}$$