fans果然不负我所望。
这程序，
帅呆了 KeyTo9_Fans能否解释一下如何由范德瓦尔登定理得出留下的点不足$O(n^2)$
hujunhua 发表于 2012-6-4 22:57 http://bbs.emath.ac.cn/images/common/back.gif
首先将$1$维的范德瓦尔登定理推广至$2$维。
然后根据$2$维的范德瓦尔登定理得：
给定正整数$k$，存在足够大的$N$，使得用$k$种颜色都无法将$N\times N$的点阵染成没有同色正方形的染色方案。
所以对于足够大的$N$，无法找到$O(n^2)$个不包含正方形的点。 看这个帖子这么火，就来凑热闹，呵呵。
先贴结果，如图。
其中左面4列应该没有什么异议，r对应那些红点的数量，b对应黑点，你懂的。表中列出的是我这里已有的最好的结果。所谓最好，就是r尽量小，b尽量大，且能构造。我总是这么啰嗦，呵呵。
算法是贪婪地，最贪的选择是随机地，这两点中的任意一点就使得结果无法保证为最优。呵呵。
实现是用Mathematica地，代码是如下地：n=16
t0=Flatten,1];
t1=Flatten,{k,2,n}],3];
t2=Map -> Last[#] &, Transpose[{t0, Range]}]];
t3=Union];
t3//Length这一段是为了产生f个正方形，存在t3里输出。mm=100;t1=Range;sss={};
Do->Last[#]&,Transpose[{RandomSample,t1}]];
s0=t3/.t2;ss={};
While[s0!={},
ks=Last]]]]];AppendTo;
s0=Select&];];AppendTo];,{mm}];
Unionmm是可以加大地，开头那里是可以优化为PermutationReplace地（我这里的版本低），结果是可以改为输出地。
呵呵。 有了zgg的数据和47#KeyTo9_Fans的对比，我对49#KeyTo9_Fans所说“使尽十八般武器”所历经的艰辛才有了一点感性认识。
只是，这个数列至此才确定了前6项，太少了点。没料到计算复杂度会这么大，难道就此搁浅了么？ 63# zgg___
帅呆了！
zgg的代码启发了我，
我看能不能改一下贪心的策略。 zgg在63楼的和Fans在47楼给的的有点差别。
在n=10时，开始分道扬镳了。
Fans可否给出n=10时，r=51的数据？
zgg能给出r=52的方案：
63# zgg___
太棒了。
Sort]] 比 Tally 效率高多了 64#wayne
虽然zgg___和KeyTo9_Fans的前9项数据相同，但是按47#KeyTo9_Fans的说明，只有前6项数据是确定无改的，而n>6以后的数据都可能有进一步优化的空间。
我猜想，对于n<=6，KeyTo9_Fans一定是使用了穷举算法，对于n>6，则使用了类似于贪心算法的优化算法。 使用41#wayne的程序计算了n=9时点（x,y）所关联的正方形数，结果如下图：
51#所写的公式在奇数的情况下仍然成立，原点仍然在大正方形中心，这时点(x,y)的坐标都是半整数。比如图中标识49的点的坐标为（±1/2,±1/2）
点(x,y)关联的正方形
综合41#、51#和69# 的结果，边长为 n 的正方形点阵中，格点(x,y)所关联的正方形数Qt(x,y)如下：1、若以正方形的中心为原点，那么Qt(x,y)={n(n+2)}/2-(x^2+y^2).需要注意的是，当 n 为奇数时，格点坐标 x, y 均为半整数。
2、若以正方形的左下角为原点，那么Qt(x,y)=n+x(n-x)+y(n-y).
原点取在中心时，Qt(x, y)=n(n+2)/2-r^2, 这里r=\sqrt{x^2+y^2}，为格点到中心的距离。
原点取在左下时，格点坐标 x, y 取 0~n 的自然数，不出现半整数。
两种坐标系各有千秋。