对于每个正整数 $n$，将 $n$ 表示成 $2$ 的非负整数次方之和．令 $f(n)$ 为正整数 $n$ 的不同表示法的个数．
如果两个表示法的差别仅在于它们中各个数相加的次序不同，这两个表示法就被视为是相同的．例如，$f(4)=4$，因为 $4$ 恰有下列四种表示法：$4;2+2;2+1+1;1+1+1+1$．
求证：对于任意整数 $n\geqslant3,{{2}^{\frac{{{n}^{2}}}{4}}}<f({{2}^{n}})<{{2}^{\frac{{{n}^{2}}}{2}}}$．（立陶宛）
如果两个表示法的差别仅在于它们中各个数相加的次序不同，这两个表示法就被视为是相同的．例如，$f(4)=4$，因为 $4$ 恰有下列四种表示法：$4;2+2;2+1+1;1+1+1+1$．
求证：对于任意整数 $n\geqslant3,{{2}^{\frac{{{n}^{2}}}{4}}}<f({{2}^{n}})<{{2}^{\frac{{{n}^{2}}}{2}}}$．（立陶宛）
【难度】
【出处】
1997年第38届IMO试题
【标注】
【答案】
略
【解析】
对于任意一个大于 $1$ 的奇数 $n$，令 $n=2k+1$，$n$ 的任一表示中必含有一个 $1$，去掉这个 $1$ 就得到 $2k$ 的一个表示；反之，给 $2k$ 的任一表示加上一个 $1$，就得到 $2k+1$ 的一个表示．这是 $2k+1$ 与 $2k$ 的表示之间的一个一一对应．从而有 $f(2k+1)=f(2k)$ ①
对于任意正偶数 $n=2k$，其表示可以分为两类：含有 $1$ 的与不含 $1$ 的．对于前者，去掉一个 $1$ 就得到 $2k-1$ 的一个表示；对于后者，将每一项除以 $2$，就得到 $k$ 的一个表示．这两种变换都是可逆的，从而都是一一对应．于是得到第二个递归式：$f(2k)=f(2k-1)+f(k)$ ②
①，② 式对于任意 $k\geqslant 1$ 都成立．显然 $f(1)=1$．定义 $f(0)=1$，则 ① 式对于 $k=0$ 也成立．根据 ①，② 式，函数 $f$ 是不减的．
由 ① 式，可以将 ② 式中的 $f(2k-1)$ 换成 $f(2k-2)$，得到 $f(2k)-f(2k-2)=f(k),k=1,2,3,\cdots,n$ 求和，得到
$f(2n)=2+f(2)+f(3)+\cdots+f(n),n=1,2,3,\cdots$ ③
下面先证明上界，在 ③ 式中，右端所有的项都不大于最后一项，对于 $n\geqslant 2,2=f(2)\leqslant f(n)$．于是有
$\begin{aligned}f(2n)&=2+(f(2)+\cdots+f(n))\\
&\leqslant 2+(n-1)f(n)\\
&\leqslant f(n)+(n-1)f(n)\\
&=nf(n)
\end{aligned}$
$n=2,3,4,\cdots$，从而得到
$\begin{aligned}f(2^n)&\leqslant 2^{n-1}\cdot f(2^{n-1})\\
&\leqslant 2^{n-1}\cdot 2^{n-2}\cdot f(2^{n-2})\\
&\leqslant 2^{n-1}\cdot 2^{n-2}\cdot 2^{n-3}\cdot f(2^{n-3})\leqslant \cdots\\
&\leqslant 2^{(n-1)+(n-2)+\cdots+1}\cdot f(2)\\
&=2^{\frac{n(n-1)}{2}}\cdot 2
\end{aligned}$
因为当 $n\geqslant 3$ 时有 $2^{\frac{n(n-1)}{2}}\cdot 2<2^{\frac{n^2}{2}}$，上界得证．
为了证明下届，我们先证明对于具有相同奇偶性的正整数 $b\geqslant a\geqslant 0$，有如下不等式成立：$f(b+1)-f(b)\geqslant f(a+1)-f(a)$ ④
事实上，如果 $a,b$ 同为偶数，则由 ① 式知上式两端均等于 $0$．而当 $a,b$ 同为奇数时，由 ② 式知 $f(b+1)-f(b)=f\left(\dfrac{b+1}{2}\right),f(a+1)-f(a)=f\left(\dfrac{a+1}{2}\right)$．由函数 $f$ 是不减的即得不等式 ④ 成立．
任取正整数 $r\geqslant k\geqslant 1$，其中 $r$ 为偶数，在 ④ 式中依次令 $a=r-j,b=r+j,j=0,1,\cdots,k-1$．然后将这些不等式加起来，得到 $f(r+k)-f(r)\geqslant f(r+1)-f(r-k+1)$．
因为 $r$ 是偶数，所以 $f(r+1)=f(r)$．从而 $f(r+k)+f(r-k+1)\geqslant 2f(r),k=1,\cdots,r$
对于 $k=1,\cdots,r$，将上述不等式相加，即得 $f(1)+f(2)+\cdots+f(2r)\geqslant 2rf(r)$，
根据 ③ 式，上式左端等于 $f(4r)-1$．从而对于任意偶数 $r\geqslant 2,f(4r)\geqslant 2rf(r)+1>2rf(r)$．取 $r=2^{m-2}$ 即得 $f(2^m)\geqslant 2^{m-1}f(2^{m-2})$．⑤
要使 $r=2^{m-2}$ 为偶数，$m$ 须为大于 $2$ 的整数，但是 ⑤ 式对于 $m=2$ 也成立．
显然 $f(2^2)=4>2^{\frac{2^2}{4}},f(2^3)=2+f(2)+f(3)+f(4)=1+1+2+2+4=10>2^{\frac{3^2}{4}}$．假设 $n\geqslant 4$ 并且对 $n-2$ 已有 $f(2^{n-2})>2^{\frac{(n-2)^2}{4}}$，则由 ⑤ $f(2^n)\geqslant 2^{n-1}f(2^{n-2})>2^{n-1+\frac{(n-2)^2}{4}}=2^{\frac{n^2}{4}}$．
因此对一切 $n\geqslant 2$ 下界成立．
对于任意正偶数 $n=2k$，其表示可以分为两类：含有 $1$ 的与不含 $1$ 的．对于前者，去掉一个 $1$ 就得到 $2k-1$ 的一个表示；对于后者，将每一项除以 $2$，就得到 $k$ 的一个表示．这两种变换都是可逆的，从而都是一一对应．于是得到第二个递归式：$f(2k)=f(2k-1)+f(k)$ ②
①，② 式对于任意 $k\geqslant 1$ 都成立．显然 $f(1)=1$．定义 $f(0)=1$，则 ① 式对于 $k=0$ 也成立．根据 ①，② 式，函数 $f$ 是不减的．
由 ① 式，可以将 ② 式中的 $f(2k-1)$ 换成 $f(2k-2)$，得到 $f(2k)-f(2k-2)=f(k),k=1,2,3,\cdots,n$ 求和，得到
$f(2n)=2+f(2)+f(3)+\cdots+f(n),n=1,2,3,\cdots$ ③
下面先证明上界，在 ③ 式中，右端所有的项都不大于最后一项，对于 $n\geqslant 2,2=f(2)\leqslant f(n)$．于是有
$\begin{aligned}f(2n)&=2+(f(2)+\cdots+f(n))\\
&\leqslant 2+(n-1)f(n)\\
&\leqslant f(n)+(n-1)f(n)\\
&=nf(n)
\end{aligned}$
$n=2,3,4,\cdots$，从而得到
$\begin{aligned}f(2^n)&\leqslant 2^{n-1}\cdot f(2^{n-1})\\
&\leqslant 2^{n-1}\cdot 2^{n-2}\cdot f(2^{n-2})\\
&\leqslant 2^{n-1}\cdot 2^{n-2}\cdot 2^{n-3}\cdot f(2^{n-3})\leqslant \cdots\\
&\leqslant 2^{(n-1)+(n-2)+\cdots+1}\cdot f(2)\\
&=2^{\frac{n(n-1)}{2}}\cdot 2
\end{aligned}$
因为当 $n\geqslant 3$ 时有 $2^{\frac{n(n-1)}{2}}\cdot 2<2^{\frac{n^2}{2}}$，上界得证．
为了证明下届，我们先证明对于具有相同奇偶性的正整数 $b\geqslant a\geqslant 0$，有如下不等式成立：$f(b+1)-f(b)\geqslant f(a+1)-f(a)$ ④
事实上，如果 $a,b$ 同为偶数，则由 ① 式知上式两端均等于 $0$．而当 $a,b$ 同为奇数时，由 ② 式知 $f(b+1)-f(b)=f\left(\dfrac{b+1}{2}\right),f(a+1)-f(a)=f\left(\dfrac{a+1}{2}\right)$．由函数 $f$ 是不减的即得不等式 ④ 成立．
任取正整数 $r\geqslant k\geqslant 1$，其中 $r$ 为偶数，在 ④ 式中依次令 $a=r-j,b=r+j,j=0,1,\cdots,k-1$．然后将这些不等式加起来，得到 $f(r+k)-f(r)\geqslant f(r+1)-f(r-k+1)$．
因为 $r$ 是偶数，所以 $f(r+1)=f(r)$．从而 $f(r+k)+f(r-k+1)\geqslant 2f(r),k=1,\cdots,r$
对于 $k=1,\cdots,r$，将上述不等式相加，即得 $f(1)+f(2)+\cdots+f(2r)\geqslant 2rf(r)$，
根据 ③ 式，上式左端等于 $f(4r)-1$．从而对于任意偶数 $r\geqslant 2,f(4r)\geqslant 2rf(r)+1>2rf(r)$．取 $r=2^{m-2}$ 即得 $f(2^m)\geqslant 2^{m-1}f(2^{m-2})$．⑤
要使 $r=2^{m-2}$ 为偶数，$m$ 须为大于 $2$ 的整数，但是 ⑤ 式对于 $m=2$ 也成立．
显然 $f(2^2)=4>2^{\frac{2^2}{4}},f(2^3)=2+f(2)+f(3)+f(4)=1+1+2+2+4=10>2^{\frac{3^2}{4}}$．假设 $n\geqslant 4$ 并且对 $n-2$ 已有 $f(2^{n-2})>2^{\frac{(n-2)^2}{4}}$，则由 ⑤ $f(2^n)\geqslant 2^{n-1}f(2^{n-2})>2^{n-1+\frac{(n-2)^2}{4}}=2^{\frac{n^2}{4}}$．
因此对一切 $n\geqslant 2$ 下界成立．
答案
解析
备注
