IV鳥取大学 2007年 数学 第IV問解答・解説

医学部医学科用 IV(B)

(1) 操作を順に行うと、次の表となる。 $$\begin{array}{c|rrrrrrr} n&2&3&4&5&6&7&8\\\hline f(n)&1&3&1&3&5&7&1 \end{array}$$ 例えば $n=5$ では $2,4,1,5$ の順に取り除かれ3が残り、$n=6$ では $2,4,6,3,1$ の順に取り除かれ5が残る。

(2) まず $2n$ 枚の場合、一周目で $2,4,\ldots,2n$ が取り除かれ、$1,3,\ldots,2n-1$ が残る。これらを順に $1,2,\ldots,n$ と読み替えると、次に取り除かれる3は新しい番号2であり、以後の操作は $n$ 枚の場合と同じである。新しい番号 $j$ は元の番号 $2j-1$ に対応するので $$\boxed{f(2n)=2f(n)-1}.$$ 次に $2n+1$ 枚の場合、一周目で $2,4,\ldots,2n$ を取り除いたあと、次に1が取り除かれる。残りは $3,5,\ldots,2n+1$ の $n$ 枚である。これらを順に $1,2,\ldots,n$ と読み替えると、次に取り除かれる5は新しい番号2に当たる。したがって新しい番号 $j$ と元の番号 $2j+1$ の対応から $$\boxed{f(2n+1)=2f(n)+1}.$$ $n=1$ では、それぞれ1枚だけ残る時点で操作が終わり、$f(2)=1, f(3)=3$ であるから両式はやはり成立する。

(3) $f(1)=1$ と(2)の偶数の場合の式を用いて数学的帰納法で示す。$n=1$ では $f(2)=1$。$f(2^n)=1$ と仮定すれば $$f(2^{n+1})=2f(2^n)-1=1.$$ よって、すべての自然数 $n$ に対して $\boxed{f(2^n)=1}$。

(4) $N_k=2^k-1$ とおくと $N_1=1$、$N_{k+1}=2N_k+1$ である。(2)より $$f(N_{k+1})=2f(N_k)+1.$$ $f(N_1)=1$ なので、帰納的に $f(N_k)=2^k-1$ となる。求める数は $$2^{10}+2^9+\cdots+2+1=2^{11}-1=N_{11}$$ だから $$\boxed{f(2^{10}+2^9+\cdots+2+1)=2^{11}-1=2047}.$$