组合数学着色数问题：求n=2时N=2^(2^(2+2))-1的反例

嗨，我来帮你构造这个反例~首先明确问题：我们要给2到65535（也就是2⁽²4)-1）的所有正整数染成红、蓝两种颜色，确保不存在同色的三个数a,b,c满足a^b=c。

先回顾核心逻辑：当N=65536时，会出现矛盾——它既是红数的幂（256²=65536，256和2都是红），又是蓝数的幂（4⁸=65536，4和8都是蓝），所以必须同时是红和蓝，这就证明了65536是最小的“nice数”。而65535以内的数，我们可以通过以下规则构造合法着色：

着色规则 #

1. 基础颜色定义：
   • 把2染成红色
   • 把4（2²）和8（2³）染成蓝色
   • 把256（2⁸，也就是4⁴）染成红色——因为如果256是蓝色，那4、4、256就都是蓝色，构成违规三元组，所以必须染红
2. 递归扩展着色：
   • 对于任何能写成a^b（a,b≥2）的数x：
     • 如果a和b都是红色，x必须染成蓝色（避免出现红+红=红的违规三元组）
     • 如果a和b都是蓝色，x必须染成红色（避免出现蓝+蓝=蓝的违规三元组）
     • 如果a红b蓝或a蓝b红，x直接染成蓝色即可（不会形成同色三元组）
   • 对于不能写成任何a^b（a,b≥2）的数（比如3、5这类质数，或者6、10这类非幂次合数），统一染成蓝色

验证合法性 #

我们检查几个关键情况：

• 红色集合里的数：2、256，还有像4096（8⁴，8和4都是蓝，所以4096染红）这类数。这些数之间的幂运算结果要么超出65535（比如2²⁵⁶、256²），要么另一个底数/指数是蓝色（比如2⁸=256，8是蓝，所以a红b蓝，不构成同色三元组）
• 蓝色集合里的数：比如4²=16（4蓝，2红，不同色）、8²=64（8蓝，2红，不同色）、4⁴=256（4蓝，4蓝，结果256红，不同色），所有可能的同色底数+指数组合，结果都被染成了相反颜色，不会出现违规的同色三元组。

这样整个2到65535的着色就完全合法，没有违规的同色三元组，这就是我们要找的反例啦~

备注：内容来源于stack exchange，提问作者Bennett