每日一题[4013]算两次

已知数列 $a_1, a_2, \cdots, a_n$ 为严格单调递增的正整数数列，$\left\{a_1, a_2, \cdots, a_n\right\}$ 的子集有 $2^n$ 个，分别计算每个子集的元素和得到 $S_1, S_2, \cdots, S_{2^n}$（规定空集元素和为 $0$），已知 $S_1<S_2<\cdots<S_{2^n}$．

1、求 $S_{2^n}$ 的最小值．

2、求 $S_1, S_2, \cdots, S_{2^n}$ 方差的最小值．

3、求证：$a_1^2+a_2^2+\cdots+a_n^2 \geqslant \dfrac{4^n-1}{3}$．

解析

1、根据题意，有 $S_1=0$，进而由 $S_1<S_2<\cdots<S_{2^n}$ 可得\[S_{2^n}=S_1+\sum_{k=1}^{2^n-1}(S_{k+1}-S_k)\geqslant 2^n-1,\]下面给出：

构造    当 $a_k=2^{k-1}$ 时，设其前 $n$ 项构成的集合为 $A_n=\{a_1,a_2,\cdots,a_n\}$，则 $A_n$ 的所有子集的元素和构成的集合\[B_n=\{0,1,2,3,4,\cdots,2^n-1\}.\]

构造的证明     对 $n$ 进行归纳．当 $n=1$ 时命题显然成立．假设命题对 $n$ 成立，则在 $n+1$ 的情形下，集合 $A_{n+1}$ 的子集可以分为两类： 第一类，不包含元素 $a_{n+1}=2^n$ 的，它们的元素和构成的集合为 $B_n$； 第二类，包含元素 $a_{n+1}=2^n$ 的，它们的元素和构成的集合为\[B_n'= \{x+2^n\mid x\in B_n\}=\{2^n,2^n+1,\cdots,2^{n+1}-1\},\] 于是就得到了\[B_{n+1}=B_n\cup B_n'=\{0,1,2,3,4,\cdots,2^n,2^n+1,\cdots,2^{n+1}-1\},\]这样就完成了归纳证明． 综上所述，$S_{2^n}$ 的最小值为 $2^n-1$．

2、先证明

引理     若数据 $x_1,x_2,\cdots,x_n$ 满足 $x_k\in\mathbb Z$（$k=1,2,\cdots,n$）且 $x_1<x_2<\cdots<x_n$，则当且仅当这些数据是连续的 $n$ 个整数时方差最小，且方差的最小值为 $\dfrac1{12}(n^2-1)$．

引理的证明    用调整法证明．若 $x_1,x_2,\cdots,x_n$ 不是连续的整数，设满足 $x_{i+1}-x_i>1$ 的最小的 $i$ 为 $k$（即在第 $k$ 个数和第 $k+1$ 个数之间产生了“气泡”），记气泡前的数据为 $X:x_1,x_2,\cdots,x_k$，气泡的长度为 $d=x_{k+1}-x_k-1$，气泡后的数据为 $Y:x_{k+1},\cdots,x_n$，将 $Y$ 调整为 $Y':x_{k+1}-d,\cdots,x_n-d$（即挤走气泡），数据 $Y,Y'$ 中的数据个数均为 $p=n-k$，则\[DY=DY',\quad EY'=EY-d,\]而根据样本合并后的方差公式\[D=\dfrac{kDX+pDY}{k+p}+\dfrac{(EX-EY)^2kp}{(k+p)^2}\]可知调整后的方差变小． 此类调整至多进行 $n-1$ 次，得到 $x_1,x_2,\cdots,x_n$ 为连续的整数，此时数据的方差不再变化，为\[\dfrac 1n\sum_{i=1}^ni^2-\left(\dfrac 1n\sum_{i=1}^ni\right)^2=\dfrac{(n+1)(2n+1)}6-\left(\dfrac{n+1}2\right)^2=\dfrac{n^2-1}{12},\]引理得证．

回到原题     $S_1, S_2, \cdots, S_{2^n}$ 方差的最小值为 $\dfrac1{12}\left(4^n-1\right)$．

3、考虑集合 $A=\left\{a_1, a_2, \cdots, a_n\right\}$ 的所有子集，其中每个元素均出现 $2^{n-1}$ 次，因此这些子集中元素和之和\[S_1+S_2+\cdots+S_{2^n}=2^{n-1}(a_1+a_2+\cdots+a_n),\]考虑集合 $A=\left\{a_1, a_2, \cdots, a_n\right\}$ 的所有包含 $a_i,a_j$（$1\leqslant i<j\leqslant n$）的子集，有 $2^{n-2}$ 个，进而有\[\begin{split} S_1^2+S_2^2+\cdots+S_{2^n}^2&=2^{n-1}(a_1^2+a_2^2+\cdots+a_n^2)+2^{n-2}\sum_{1\leqslant i<j\leqslant n}(2a_ia_j)\\ &=2^{n-1}(a_1^2+a_2^2+\cdots+a_n^2)+2^{n-2}\left((a_1+a_2+\cdots+a_n)^2-(a_1^2+a_2^2+\cdots+a_n^2)\right)\\ &=2^{n-2}(a_1^2+a_2^2+\cdots+a_n^2)+2^{n-2}\cdot \left(\dfrac{S_1+S_2+\cdots+S_{2^n}}{2^{n-1}}\right)^2\\ &=2^{n-2}(a_1^2+a_2^2+\cdots+a_n^2)+2^n\overline S^2,\end{split}\]从而\[\dfrac 14(a_1^2+a_2^2+\cdots+a_n^2)=\dfrac{S_1^2+S_2^2+\cdots+S_{2^n}}{2^n}-\overline S^2,\]其中 $\overline S$ 表示 $S_1,S_2,\cdots,S_{2^n}$ 的平均数，根据第 $(2)$ 小题的结论，有其方差\[\dfrac{S_1^2+S_2^2+\cdots+S_{2^n}}{2^n}-\overline S^2\geqslant \dfrac 1{12}(4^n-1),\]因此命题得证．

备注    一个基础的想法是尝试证明 $a_k\geqslant 2^{k-1}$（$k=1,2,\cdots,n$），而该结论较难用递推的方式进行．事实上，这个结论并不成立，例如当 $A=\{3,5,6,7\}$ 时，$a_4<2^3$．