有关数列染色的一揽子题目（猜想）
昨天无意翻到了一道数学竞赛题：题目1）将每个自然数染红蓝两色之一，求证：存在无穷自然数列a1，a2，……，an，……，满足：
a1，(a1+a2)/2，a2，(a2+a3)/2，a3，…… 都是同色的自然数
我联想到了另外两个结论，不知道能否成立：
猜想1）将每个自然数染红蓝两色之一，求证：对任意自然数M，存在长度为M的同色的等差数列
猜想2）将每个自然数染红蓝绿三色之一，求证：对任意自然数M，存在长度为M且满足题目1中的要求的同色自然数列
大家有没有兴趣讨论讨论？ 相邻的自然数可以染相同颜色吗,还是必须要间隔才行 染色是随便染的，没有限制 范德瓦尔登定理 恩，查了一下，猜想1和2果然都是范德瓦尔登定理的一些简单情形
那么就只剩下题目1了 猜想$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的蓝色等差数列 上述猜想可能与Erdos的下述猜想相矛盾：
Erdos猜想：如果一个无穷长整数序列的倒数和发散，那么其中必有任意长的算术级数。
我说可能，是因为楼上说的无穷长与这里说的任意长是有区别的。 8# hujunhua
对，就是“无穷长”和“任意长”的区别。7楼的条件如果改成任意长，则和范德瓦尔登定理也矛盾了……
如果是无穷长，我想到了一个证明：
自然数组成的无穷长等差数列 的是可列的，记这些等差数列为 A1，A2，…… ，An，……
作数列 a1，a2，……，an，……使得：
ak 是 Ak 中元素，并且ak的每一项都大于前一项的两倍
容易看出，数列ak中没有长度为3的等差数列，并且ak关于自然数的补集也不含有无穷长的等差数列
Cantor对角线大法
本帖最后由 hujunhua 于 2010-3-28 12:22 编辑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); ......
下面来构造{ak}: 其中每项不小于前项的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, ....}, 它不含任何无穷长等差数列，因为任何无穷长等差数列都至少有一项在其补集中。
页:
[1]
2