MathLabs

第4問

N0\mathbb N_0 を非負整数全体とする。f:N0→N0f:\mathbb N_0\to\mathbb N_0 を f(0)=0f(0)=0、すべての n≥0n\ge0 に対し f(2n)=2f(n)f(2n)=2f(n)、f(2n+1)=n+2f(n)f(2n+1)=n+2f(n) で定める。(a) L={n∣f(n)<f(n+1)}L=\{n\mid f(n)<f(n+1)\}、E={n∣f(n)=f(n+1)}E=\{n\mid f(n)=f(n+1)\}、G={n∣f(n)>f(n+1)}G=\{n\mid f(n)>f(n+1)\} を求めよ。(b) 各 k≥0k\ge0 について ak=max⁡{f(n):0≤n≤2k}a_k=\max\{f(n):0\le n\le2^k\} を kk の式で表せ。
ステップ 4/6: 最大値の位置を定める
前のステップ次のステップ
ak=f(2k−1)(k≥2)a_k=f(2^k-1)\quad(k\ge2)
詳しい解説

k=2k=2 では明らかである。k−1k-1 で成り立つと仮定する。0≤n≤2k0\le n\le2^k の上半分の偶数 n=2tn=2t には f(n)≤2ak−1f(n)\le2a_{k-1}。奇数 n=2t+1n=2t+1 には f(n)≤2k−1−1+2ak−1f(n)\le2^{k-1}-1+2a_{k-1}。いずれも f(2k−1)=2k−1−1+2f(2k−1−1)f(2^k-1)=2^{k-1}-1+2f(2^{k-1}-1) 以下なので、最大値は 2k−12^k-1 で達成される。