有关数列染色的一揽子题目（猜想）

本因坊算帐

昨天无意翻到了一道数学竞赛题： 题目1）将每个自然数染红蓝两色之一，求证：存在无穷自然数列a1，a2，……，an，……，满足： a1，(a1+a2)/2，a2，(a2+a3)/2，a3，…… 都是同色的自然数 我联想到了另外两个结论，不知道能否成立： 猜想1）将每个自然数染红蓝两色之一，求证：对任意自然数M，存在长度为M的同色的等差数列 猜想2）将每个自然数染红蓝绿三色之一，求证：对任意自然数M，存在长度为M且满足题目1中的要求的同色自然数列 大家有没有兴趣讨论讨论？

qianyb

相邻的自然数可以染相同颜色吗,还是必须要间隔才行

本因坊算帐

染色是随便染的，没有限制

hujunhua

范德瓦尔登定理

本因坊算帐

恩，查了一下，猜想1和2果然都是范德瓦尔登定理的一些简单情形 那么就只剩下题目1了

KeyTo9_Fans

猜想$1$是Fans的在百度数学吧的原创题目之一。 Fans发现这个结论自以为很了不起。 不仅如此，Fans还将猜想的结论推广为任意种颜色。 然后编程序求解最长的不存在长度为M的同色的等差数列的$01$串（$0$和$1$表示$2$种不同的颜色）。 从$M=2$开始做起，一直做到$M=5$，结果如下： | M |1|2|3| 4 | 5 | |最大长度|0|2|8|34|177| 为了求解$M=6$的结果，我每天都在跑程序。 跑了$3$个多月，也没能把结果跑出来，只好放弃。 当我把贴子发出之后，同楼主的下场一样，被人说一句“范德瓦尔登定理”就完事了，所做的工作全部作废。 我到在线整数数列百科大全上面一查，果然有这个数列： http://www.research.att.com/~njas/sequences/A121894 名字就叫范德瓦尔登数。 而且有人在$2007$年$7$月$29$日把$M=6$的结果跑出来了。 我还比这个时间提前了$8$个月开跑的呢。 只可惜水平不足，算法效率太差，比不过人家。

本因坊算帐

恩，多谢提供资料 忽然想到了下面的命题，不知道是不是又已经有人讨论过了？ 求证：存在自然数的红蓝染色方案，使得不存在无限长的红色等差数列，也不存在长度为3的蓝色等差数列

hujunhua

上述猜想可能与Erdos的下述猜想相矛盾： Erdos猜想：如果一个无穷长整数序列的倒数和发散，那么其中必有任意长的算术级数。 我说可能，是因为楼上说的无穷长与这里说的任意长是有区别的。

本因坊算帐

8# hujunhua 对，就是“无穷长”和“任意长”的区别。7楼的条件如果改成任意长，则和范德瓦尔登定理也矛盾了…… 如果是无穷长，我想到了一个证明： 自然数组成的无穷长等差数列 的是可列的，记这些等差数列为 A1，A2，…… ，An，…… 作数列 a1，a2，……，an，…… 使得： ak 是 Ak 中元素，并且ak的每一项都大于前一项的两倍 容易看出，数列ak中没有长度为3的等差数列，并且ak关于自然数的补集也不含有无穷长的等差数列

hujunhua

Cantor对角线大法，不错。试着构造一个看看。 整数项等差数列（不包括常数数列）可以用自然数有序对（a, d）表示，a为首项，d为公差。即全体整数项等差数列集等于N×N. 把这个集合按字典法排序，但第1索引选为a+d, 第2索引选为a. 排起来就是： (1, 1); (1,2), (2,1); (1,3), (2,2,), (3,1); (1, 4), (2, 3), (3, 2), (4,1); (1,5), (2, 4), (3,3), (4,2), (5, 1); ...... 下面来构造{a_k}: 其中每项不小于前项的2倍即可。 a1=1----------------------------------------选自(1,1)的首项。(1,1)就是N。 a2=3---------------------------------------选自(1,2)的次项。(1,2)即奇数列。 a3=6---------------------------------------选自(2,1)，即断头的N，{2,3,4,5,6,...} a4=13-------------------------------------选自(1,3), 即3n+1形 a5=26-------------------------------------选自(2,2), 即偶数列 a6=52-------------------------------------选自(3,1), 即断头N，{3,4,5,6,7, ...} a7=105-----------------------------------选自(1,4), 即4n+1形 a8=212-----------------------------------选自(2,3) a9=425-----------------------------------选自{3,5,7,9,...} a10=850---------------------------------选自{4,5,6,7,...} a11=1701--------------------------------选自(1,5), 即5n+1形 a12=3402-------------------------------选自(2,4) a13=6804-------------------------------选自(3,3), 即3 n形 a14=13608-----------------------------选自(4,2), 即{4,6,8,10, ...} a15=27216-----------------------------选自(5,1), 即断头N，{5,6,7,8,9, ...} ................. 其补集就是{2, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, ....}, 它不含任何无穷长等差数列，因为任何无穷长等差数列都至少有一项在其补集中。