对前 n 个正整数用 k 种颜色染色,使得无法从中选出三个不同色的正整数构成等差数列,设 k 的最大值为 f(n),求证:log3n⩽f(n)⩽log2n+1.
解析 设 v(n,p) 为正整数 n 中素数 p 的幂次,即pv(n,p)∣∣n.对于任意的正整数 m(1⩽m⩽n),将 m 染成第 v(m,3)+1 种颜色,这样就用了 ⌊log3n⌋+1 种颜色.此时对于任意不同色的正整数 x,y,有v(2x−y,3)=v(2y−x,3)=min因此 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.