本因坊算帐 发表于 2010-3-23 12:24:06

有关数列染色的一揽子题目(猜想)

昨天无意翻到了一道数学竞赛题:

题目1)将每个自然数染红蓝两色之一,求证:存在无穷自然数列a1,a2,……,an,……,满足:
a1,(a1+a2)/2,a2,(a2+a3)/2,a3,…… 都是同色的自然数

我联想到了另外两个结论,不知道能否成立:

猜想1)将每个自然数染红蓝两色之一,求证:对任意自然数M,存在长度为M的同色的等差数列

猜想2)将每个自然数染红蓝绿三色之一,求证:对任意自然数M,存在长度为M且满足题目1中的要求的同色自然数列

大家有没有兴趣讨论讨论?

qianyb 发表于 2010-3-23 13:08:30

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

本因坊算帐 发表于 2010-3-23 13:19:24

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

hujunhua 发表于 2010-3-23 13:31:09

范德瓦尔登定理

本因坊算帐 发表于 2010-3-23 14:14:36

恩,查了一下,猜想1和2果然都是范德瓦尔登定理的一些简单情形

那么就只剩下题目1了

KeyTo9_Fans 发表于 2010-3-23 17:04:07

猜想$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$个月开跑的呢。

只可惜水平不足,算法效率太差,比不过人家。

本因坊算帐 发表于 2010-3-23 17:54:31

恩,多谢提供资料

忽然想到了下面的命题,不知道是不是又已经有人讨论过了?

求证:存在自然数的红蓝染色方案,使得不存在无限长的红色等差数列,也不存在长度为3的蓝色等差数列

hujunhua 发表于 2010-3-27 13:33:28

上述猜想可能与Erdos的下述猜想相矛盾:
Erdos猜想:如果一个无穷长整数序列的倒数和发散,那么其中必有任意长的算术级数。

我说可能,是因为楼上说的无穷长与这里说的任意长是有区别的。

本因坊算帐 发表于 2010-3-27 17:52:39

8# hujunhua


对,就是“无穷长”和“任意长”的区别。7楼的条件如果改成任意长,则和范德瓦尔登定理也矛盾了……

如果是无穷长,我想到了一个证明:

自然数组成的无穷长等差数列 的是可列的,记这些等差数列为 A1,A2,…… ,An,……

作数列 a1,a2,……,an,……使得:
ak 是 Ak 中元素,并且ak的每一项都大于前一项的两倍

容易看出,数列ak中没有长度为3的等差数列,并且ak关于自然数的补集也不含有无穷长的等差数列

hujunhua 发表于 2010-3-28 10:53:29

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
查看完整版本: 有关数列染色的一揽子题目(猜想)