每日一题[2135]够不着

对前 $n$ 个正整数用 $k$ 种颜色染色，使得无法从中选出三个不同色的正整数构成等差数列，设 $k$ 的最大值为 $f(n)$，求证： $${\log_3}n\leqslant f(n)\leqslant {\log_2}n+1.$$

解析    设 $v(n,p)$ 为正整数 $n$ 中素数 $p$ 的幂次，即 $$p^{v(n,p)}\mid\mid n.$$ 对于任意的正整数 $m$（$1\leqslant m\leqslant n$），将 $m$ 染成第 $v(m,3)+1$ 种颜色，这样就用了 $\left\lfloor {\log_3}n\right\rfloor+1$ 种颜色．此时对于任意不同色的正整数 $x,y$，有 $$v(2x -y,3)=v(2y-x,3)=\min\{v(x,3),v(y,3)\},$$ 因此 $2x-y$ 和 $2y-x$ 均与 $x,y$ 之一同色，符合题意．这样就证明了 $$f(n)\geqslant \left\lfloor {\log_3}n\right\rfloor+1>{\log_3}n.$$ 接下来设 $2^k\leqslant n<2^{k+1}$（$k\in\mathbb N^{\ast}$），则右侧不等式即 $$f(n)\leqslant k+1.$$ 对 $k$ 进行归纳，应用数学归纳法证明． 当 $k=1$ 时，$n=2,3$，此时 $f(n)=2$，命题成立． 假设命题对 $k-1$ 成立，对已有 $1,2,\cdots,2^k-1$ 的染色，考虑 $1,2,\cdots,n$ 的染色，若其中有两种或以上新增的颜色，不妨设为红色和蓝色，且最小的红色数为 $x$，最小的蓝色数为 $y$，且 $x<y$，则 $$2^k\leqslant x<y\leqslant n<2^{k+1}\implies 2x-y>0,$$ 考虑正整数 $2x-y$，它与异色数对 $(x,y)$ 成等差数列，于是必然与 $x,y$ 之一同色，但 $2x-y<x<y$，这与之前假设的 $x,y$ 的最小性矛盾．因此 $1,2,\cdots,n$ 的染色至多在之前的基础上增加 $1$ 种，从而命题得证． 综上所述，有 ${\log_3}n\leqslant f(n)\leqslant {\log_2}n+1$．