|
|
这和 09 年国集选拔差不多, 当时是让证明 $\{2^a+3^b\}$ 中等差数列长度不超过 $40$. 下面就此题给出更强的结论: 等差数列长度由 $1+n^{n+(o\log n)}$ 估计.
一楼题目可以改写如下: 记 $S_i:=\{a_i^p\}_{p\in \mathbb N}$, 求证 $S_1+\cdots +S_n$ 的等差数列长度具有由 $n$ 决定的上界.
我们其实可以抛弃具体的 $S_i$, 直接令 $S_i$ 是满足如下性质的集合:
$$
\exists C_i>0\text{ 使得 }|S_i\cap [x,2x]|\leq C_i\quad (\forall x\in \mathbb R_+).
$$
我们取个名字, 称 $S_i$ 是 $C_i$-对数增长的. 取 $C_i$ 中最大值 $C_0$.
对于 $S_1+\cdots +S_n$ 中有限且单调递增的等差数列 $\{a_i\}_{i=0}^m$, 其中
$$
a_i=a_i^{(1)}+\cdots +a_i^{(n)}\quad (a_i^{(k)}\in S_k).
$$
记 $h$ 为公差, 则 $a_m-a_0=hm$. 则
$$
\begin{matrix}
\text{称 }a_i^{(k)}\text{ 是}&\text{小的}&\text{中的}&\text{大的}\\
\text{若 }a_i^{(k)}\in& (0,\frac{h}{2n})& [\frac{h}{2n},hm]& (hm,\infty)
\end{matrix}.
$$
对任意 $a_i$, 不妨设 $a_i^{(\sigma(1))}\geq a_i^{(\sigma(2))}\geq \cdots\geq a_i^{(\sigma(n))}$, 其中 $\sigma$ 是 $(1,\ldots ,n)$ 的某一置换. 不妨设 $a_i^{(\sigma(s_0))}$ 是最小的最大项, 则对任意 $1\leq s\leq s_0-1$. 直接地, 有
$$
\dfrac{a_1-\left(a_i^{(\sigma(1))}+\cdots a_i^{(\sigma(s))}\right)}{n-s}\leq a_i^{(\sigma(s+1))}\leq a_m-\left(a_i^{(\sigma(1))}+\cdots a_i^{(\sigma(s))}\right).
$$
我们记最右项 $R:=a_m-\left(a_i^{(\sigma(1))}+\cdots a_i^{(\sigma(s))}\right)$. 则上式表明
$$
R\leq (n-s)a_i^{(\sigma(s+1))}+hm\leq (n-s+1)a_i^{(\sigma(s+1))}.
$$
因此 $a_i^{(\sigma(s+1))}$ 可取的项在 $S_{\sigma(s+1)}\cap [R/(n-s+1),R]$ 中. 根据 $S_k$ 的对数增长性, $a_i^{(\sigma(s+1))}$ 取法数上界为
$$
C_0\cdot \log_2(n-s+1).
$$
随后观察中的项, 例如中的项 $a_i^{(k)}$ 满足
$$
a_i^{(k)}\in S_k\cap [h/2n,hm]
$$
从而 $a_i^{(k)}$ 的取法数上界为 $C_0\cdot \log_2(2mn)$.
小的项可以忽略不记, 毕竟 $n$ 个小的项之和也不超过公差 $h$ 的一半.
综上,
$$
m\leq 3^n\cdot \left\{C_0\cdot \max \left[\sum_{s=1}^n\log_2(n-s+1),n\log_2(2mn)\right]\right\}^n.
$$
从而这样的 $m$ 当然有仅与 $n$ 相关的上界. 若 $m$ 无上界, 则右式的 $\mathcal O(\log^n m)$ 增长小于左式的线性增长 $\mathcal O(m)$, 矛盾.
然后尝试求解 $m$ 的上界.
若 $m\leq \dfrac{(n-1)!}{2^{n+1}}\sim (n/2e)^n$, 则
$$
m\leq (3C_0\log_2 n!)^n \sim (3C_0[\log_2\sqrt{2\pi n}+n\log_2(n/e)])^n
$$
若 $m\geq \dfrac{(n-1)!}{2^{n+1}}$, 则
$$
m\leq (3C_0 n\log_2(2mn))^n=n^{n(1+\ln3C_0/\ln n+\ln [\log_2(2mn)-n])}
$$
记 $m=n^{f(n)}$, 则
$$
f(n)\ln n\leq n\ln(3C_0n)+n\ln[1+(f(n)+1)\log_2n]\leq n\ln(3C_0n)+n(f(n)+1)\log_2n
$$
从而
$$
f(n)\leq n\cdot \dfrac{\ln(3C_0)+\ln n+\log_2n}{\ln n-n\log_2 n}
$$
解得 $m\leq n^{\dfrac{n\ln(3C_0n)+n\log_2n}{\ln n-n\log_2 n}}\sim n^{n+ o(\ln n)}$.
|
|
Czhang271828
Posted 2023-6-5 16:24
