趣题:对全体正整数红蓝二着色使之不含单色无穷等差数列

    你认为,是否有可能把全体正整数染成红蓝二色,使得不存在无穷等差数列,数列中的所有数都是一种颜色?如果你认为存在这样的染色方案,请给出一个构造方法;如果你认为不存在,证明之。在看下面的答案之前,不妨先仔细思考一下。

    事实上,满足题意的染色方案是存在的,构造方法非常简单,非常直接,非常暴力。显然,无穷等差数列只有可数个,不妨把它们分别叫做A_1, A_2, A_3, …。现在,如果我们能够构造两个数列r_1, r_2, r_3, …和b_1, b_2, b_3…,使得对于每一个i,r_i和b_i都在数列A_i中,并且r数列中的每个数都和b数列中的所有数都不相同。这样,把r数列中的所有数染成红色,把b数列中的所有数染成蓝色(其它未出现的数随意染色),就能保证每个无穷等差数列都包含了至少两种颜色。
    而这样的r数列和b数列显然存在,因为每一次选择新的r_i和b_i时,无穷数列A_i中都只有有限个数不能选,因此r_i和b_i永远都有选的。

    Update: 地基层网友给出了一个更巧妙、更简单的构造方法:对全体正整数倍长间隔染色,即把1染成红色,2和3染成蓝色,4到7染成红色,8到15染成蓝色……。显然,当染色区间的长度大于公差时,等差数列最终都将一截一截地落在不同的染色区间中。

Read more…

预告:几个有趣的编程比赛

刚过完年回到家,也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件,邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍,这些比赛还是挺有意思的,这里向大家推荐一下。

http://felicity.iiit.ac.in/codecraft/
CodeCraft,举办了两三年了,一个传统方式的编程比赛。
测试赛:14th Feb, 6pm – 8pm IST (GMT +5:30).
正式比赛:15th Feb, 2pm – 10pm IST (GMT +5:30).

http://felicity.iiit.ac.in/~math/
MathematiKa,已经举办过一年了,这是第二年的比赛。比赛共12道数学题,你只需要提交答案即可。例如,去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时,把所有30个数从小到大连接在一起即可。最大的那个x有十几位,因此这题硬算是不行的。
测试赛:12th Feb, 6pm – 9pm IST (GMT +5:30).
正式比赛:13th Feb, 2pm – 10pm IST (GMT +5:30)

Read more…

用计算机自动作曲?Wolfram的手机铃声生成算法

    随着计算机科学的发展,越来越多的人开始思考,人工智能到底能强到什么地步?是否会有一天,我们可以完全通过计算机算法生成一部想象力丰富、情节跌宕起伏的科幻小说?“写作机器”或许离我们还有些遥远,不过用计算机来自动作曲已经有了一些像模像样的算法了。网友digiter分享了一个非常有意思的站点WolframTones,它是Wolfram的一个有趣的项目:用程序算法随机生成一段动听的音乐(用来当手机铃声)。随便点击一个Style,系统会自动生成一段音乐,而且每次生成的都不一样。程序的算法简单得简直让人不敢相信:随机生成一组初始编码(第一列),然后按照一些简单的“生命游戏低维版”式的规则不断迭代生成出余下列的编码,再将这些编码与各音高一一对应起来。难以置信的是,这样简单的算法居然能产生出如此和谐动听的旋律,科学与艺术奇迹般地结合在了一起。