トップ› 東北大学› 2001年› 理系第3問

東北大学 2001年理系第3問解説

方針・初手

得点は、引いた整数 $n$ を $2$ で割れるだけ割ったときに残る奇数、すなわち $n$ の最大奇約数である。

そこで、$n$ の得点を $a_n$ とおくと、偶数と奇数で

$$ a_{2k-1}=2k-1,\qquad a_{2k}=a_k $$

が成り立つ。これを用いて、総和

$$ S(N)=\sum_{n=1}^{N} a_n $$

を漸化的に求めれば、期待値は $S(200)/200$ で求まる。

解法1

$n$ の得点を $a_n$ とする。

奇数 $2k-1$ はそのまま得点になるので

$$ a_{2k-1}=2k-1 $$

である。また、偶数 $2k$ は $2$ で1回割ると $k$ になるから、$2k$ の得点は $k$ の得点と同じであり、

$$ a_{2k}=a_k $$

である。

ここで

$$ S(N)=\sum_{n=1}^{N} a_n $$

とおく。

$N=2m$ のとき、奇数番目と偶数番目に分けると

$$ \begin{aligned} S(2m) &=\sum_{k=1}^{m} a_{2k-1}+\sum_{k=1}^{m} a_{2k} \\ &=\sum_{k=1}^{m} (2k-1)+\sum_{k=1}^{m} a_k \\ &=m^2+S(m) \end{aligned} $$

となる。

同様に、$N=2m+1$ のときは

$$ S(2m+1)=\sum_{k=1}^{m+1}(2k-1)+\sum_{k=1}^{m}a_k=(m+1)^2+S(m) $$

である。

これを順に用いると、

$$ \begin{aligned} S(200)&=100^2+S(100),\\ S(100)&=50^2+S(50),\\ S(50)&=25^2+S(25),\\ S(25)&=13^2+S(12),\\ S(12)&=6^2+S(6),\\ S(6)&=3^2+S(3),\\ S(3)&=2^2+S(1),\\ S(1)&=1 \end{aligned} $$

である。

したがって、

$$ \begin{aligned} S(3)&=4+1=5,\\ S(6)&=9+5=14,\\ S(12)&=36+14=50,\\ S(25)&=169+50=219,\\ S(50)&=625+219=844,\\ S(100)&=2500+844=3344,\\ S(200)&=10000+3344=13344 \end{aligned} $$

となる。

よって、求める期待値は

$$ \frac{S(200)}{200} =\frac{13344}{200} =\frac{1668}{25} $$

である。

解法2

得点になりうる数は奇数のみである。奇数 $m$ に対し、得点が $m$ になるのは

$$ m,\ 2m,\ 4m,\ 8m,\ \dots $$

のうち $200$ 以下のものを引いたときである。

したがって、得点の総和は

$$ \sum_{\substack{m\leqq 199\ m:\text{奇数}}} m\cdot #{,k\geqq 0\mid 2^k m\leqq 200,} $$

で与えられる。

これを $m$ の範囲ごとに整理する。

(i)

$101\leqq m\leqq 199$ の奇数では $2m>200$ であるから、寄与回数は $1$ 回である。

(ii)

$51\leqq m\leqq 99$ の奇数では $m,2m\leqq 200$ だが $4m>200$ なので、寄与回数は $2$ 回である。

(iii)

$25\leqq m\leqq 49$ の奇数では寄与回数は $3$ 回である。

(iv)

$13\leqq m\leqq 23$ の奇数では寄与回数は $4$ 回である。

(v)

$7\leqq m\leqq 11$ の奇数では寄与回数は $5$ 回である。

(vi)

$5$ では寄与回数は $6$ 回、$3$ では $7$ 回、$1$ では $8$ 回である。

したがって総和は

$$ \begin{aligned} &\sum_{\substack{101\leqq m\leqq 199\ m:\text{奇数}}} m +2\sum_{\substack{51\leqq m\leqq 99\ m:\text{奇数}}} m +3\sum_{\substack{25\leqq m\leqq 49\ m:\text{奇数}}} m \\ &\qquad +4\sum_{\substack{13\leqq m\leqq 23\ m:\text{奇数}}} m +5\sum_{\substack{7\leqq m\leqq 11\ m:\text{奇数}}} m +6\cdot 5+7\cdot 3+8\cdot 1 \end{aligned} $$

である。

各和を計算すると、

$$ \begin{aligned} \sum_{\substack{101\leqq m\leqq 199\ m:\text{奇数}}} m &=7500,\\ \sum_{\substack{51\leqq m\leqq 99\ m:\text{奇数}}} m &=1875,\\ \sum_{\substack{25\leqq m\leqq 49\ m:\text{奇数}}} m &=444,\\ \sum_{\substack{13\leqq m\leqq 23\ m:\text{奇数}}} m &=108,\\ \sum_{\substack{7\leqq m\leqq 11\ m:\text{奇数}}} m &=27 \end{aligned} $$

より、

$$ 7500+2\cdot 1875+3\cdot 444+4\cdot 108+5\cdot 27+30+21+8=13344 $$

となる。

よって期待値は

$$ \frac{13344}{200}=\frac{1668}{25} $$

である。