格点正方形，可否发现一个新数列？

wayne

52# KeyTo9_Fans fans果然不负我所望。 这程序， 帅呆了

KeyTo9_Fans

KeyTo9_Fans能否解释一下如何由范德瓦尔登定理得出留下的点不足$O(n^2)$ hujunhua 发表于 2012-6-4 22:57

首先将$1$维的范德瓦尔登定理推广至$2$维。 然后根据$2$维的范德瓦尔登定理得： 给定正整数$k$，存在足够大的$N$，使得用$k$种颜色都无法将$N\times N$的点阵染成没有同色正方形的染色方案。 所以对于足够大的$N$，无法找到$O(n^2)$个不包含正方形的点。

zgg___

看这个帖子这么火，就来凑热闹，呵呵。 先贴结果，如图。 其中左面4列应该没有什么异议，r对应那些红点的数量，b对应黑点，你懂的。表中列出的是我这里已有的最好的结果。所谓最好，就是r尽量小，b尽量大，且能构造。我总是这么啰嗦，呵呵。 算法是贪婪地，最贪的选择是随机地，这两点中的任意一点就使得结果无法保证为最优。呵呵。 实现是用Mathematica地，代码是如下地：

1. n=16
2. t0=Flatten[Table[{i,j},{i,n},{j,n}],1];
3. t1=Flatten[Table[Table[{{i-1+x,y},{k-1+x,i-1+y},{k-i+x,k-1+y},{x,k-i+y}},{i,k},{x,n-k+1},{y,n-k+1}],{k,2,n}],3];
4. t2=Map[First[#] -> Last[#] &, Transpose[{t0, Range[Length[t0]]}]];
5. t3=Union[Map[Sort, t1 /. t2]];
6. t3//Length

复制代码

这一段是为了产生f个正方形，存在t3里输出。

1. mm=100;t1=Range[n^2];sss={};
2. Do[t2=Map[First[#]->Last[#]&,Transpose[{RandomSample[t1],t1}]];
3. s0=t3/.t2;ss={};
4. While[s0!={},
5. ks=Last[Last[Sort[Split[Sort[Flatten[s0]]]]]];AppendTo[ss, ks];
6. s0=Select[s0,!MemberQ[#,ks]&];];AppendTo[sss,Length[ss]];,{mm}];
7. Union[sss]

复制代码

mm是可以加大地，开头那里是可以优化为PermutationReplace地（我这里的版本低），结果是可以改为输出地。 呵呵。

hujunhua

有了zgg的数据和47#KeyTo9_Fans的对比，我对49#KeyTo9_Fans所说“使尽十八般武器”所历经的艰辛才有了一点感性认识。 只是，这个数列至此才确定了前6项，太少了点。没料到计算复杂度会这么大，难道就此搁浅了么？

wayne

63# zgg___ 帅呆了！ zgg的代码启发了我， 我看能不能改一下贪心的策略。

wayne

zgg在63楼的和Fans在47楼给的的有点差别。 在n=10时，开始分道扬镳了。 Fans可否给出n=10时，r=51的数据？ zgg能给出r=52的方案：

wayne

63# zgg___ 太棒了。 Sort[Split[Sort]] 比 Tally 效率高多了

hujunhua

64#wayne 虽然zgg___和KeyTo9_Fans的前9项数据相同，但是按47#KeyTo9_Fans的说明，只有前6项数据是确定无改的，而n>6以后的数据都可能有进一步优化的空间。 我猜想，对于n<=6，KeyTo9_Fans一定是使用了穷举算法，对于n>6，则使用了类似于贪心算法的优化算法。

hujunhua

使用41#wayne的程序计算了n=9时点（x,y）所关联的正方形数，结果如下图： 51#所写的公式在奇数的情况下仍然成立，原点仍然在大正方形中心，这时点(x,y)的坐标都是半整数。比如图中标识49的点的坐标为（±1/2,±1/2）

hujunhua

综合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 的自然数，不出现半整数。 两种坐标系各有千秋。