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