每日一题[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$.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论