将正整数 的每一个都染成红色或者蓝色,并且每一种颜色的数至少一个。 若红色数中的每一个数都是两个不同的蓝色数的和,蓝色数中的每一个数都是两个红色数的差, 求 的最小可能值。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
先独立尝试,再展开工具说明与想法来源。
极端元素法指先利用最小或最大元素的必要条件,强迫其他元素的位置或类别。这里两个加数必须不同,尤其要排除用同一个中间数相加的伪构造。
想法从哪来:两色互相提供和、差,直接猜着色缺少停止标准。先追问最小红数至少多大,以及最大蓝数至多多大:红数是两个不同正数之和,给出前者;任一红数差不超过最大数减最小红数,给出后者。于是开头一段必须蓝,结尾一段必须红,两端的强制色就产生夹逼。 为了找最小规模,先在一个较小上界内用夹逼压缩最小红数的可能值,然后检查最大数能否拆成两个不同蓝数。这样只剩很短的有限讨论。最后再寻找一个略大的着色,并对每个红数列一组蓝和、每个蓝数列一组红差;一个构造必须同时通过两个方向。
设最小红数为 。红数由两个不同蓝数相加迫使 ;蓝数由两个红数作差 又给出统一上界 。这两个极端约束把 时的 压缩到 两个情形,可以完全排除;随后给出 的着色构造。
设红色数集合为 ,蓝色数集合为 ,并令
因为 是两个不同正整数之和,所以 。另一方面,每个蓝色数 都是两个红色数之差;把较大者减去较小者,可知对任意 ,
特别地,所有大于 的数都是红色,故 。又因 是蓝色, 由(1)有
即 。
假设 ,则 ,所以只可能有 或 。
若 ,由(1)知 都是红色,且 。 当 时,把 写成两个不同正整数之和的所有可能分别为
( 不合“两个不同”)。每一行的每一种写法都至少含有 或 中的一个红色数,故红色数 不能表示成两个不同蓝色数之和,矛盾。
若 ,则 。在 下,由(1)所有蓝色数都不超过 ;又 为红色,所以蓝色数只能取自 。 两个不同蓝色数之和至多为 ,仍与 矛盾。 因此 。
当 时,取
红色数可分别表示为
而蓝色数可分别表示为
所有条件均满足。故最小可能值为
下界证明没有假设差的顺序:蓝色数为正,故总可把较大的红数减去较小的红数。 构造中两种颜色均非空,每个和都使用两个不同蓝数,每个差也使用两个不同红数。
双向“和—差”染色条件应先研究两色的极小元和极大元。最小红数控制蓝色初段, 而红数差控制蓝色上界;夹逼后只剩少量边界情形,最后用显式构造证明下界可达。
取最小红数后推出最高一段全红,压缩到两种最小红数及有限规模,排除小例还需构造9个数的完整双色和差表示。
已记下,谢谢!