数学研发论坛

 找回密码
 欢迎注册
楼主: hujunhua

[提问] 格点正方形,可否发现一个新数列?

[复制链接]
发表于 2012-6-6 14:17:18 | 显示全部楼层
52# KeyTo9_Fans
fans果然不负我所望。
这程序,
帅呆了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-7 12:35:46 | 显示全部楼层
KeyTo9_Fans能否解释一下如何由范德瓦尔登定理得出留下的点不足$O(n^2)$
hujunhua 发表于 2012-6-4 22:57


首先将$1$维的范德瓦尔登定理推广至$2$维。

然后根据$2$维的范德瓦尔登定理得:

给定正整数$k$,存在足够大的$N$,使得用$k$种颜色都无法将$N\times N$的点阵染成没有同色正方形的染色方案。

所以对于足够大的$N$,无法找到$O(n^2)$个不包含正方形的点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-8 16:51:42 | 显示全部楼层
看这个帖子这么火,就来凑热闹,呵呵。
先贴结果,如图。
fan1.JPG
其中左面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地(我这里的版本低),结果是可以改为输出地。
呵呵。

评分

参与人数 2威望 +20 金币 +12 贡献 +20 经验 +20 鲜花 +20 收起 理由
wayne + 12 + 12 + 12 + 12 + 12 精彩极了!
hujunhua + 8 + 8 + 8 + 8 贪心算法的成绩也不错

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-6-8 20:06:36 | 显示全部楼层
有了zgg的数据和47#KeyTo9_Fans的对比,我对49#KeyTo9_Fans所说“使尽十八般武器”所历经的艰辛才有了一点感性认识。
只是,这个数列至此才确定了前6项,太少了点。没料到计算复杂度会这么大,难道就此搁浅了么?

评分

参与人数 1鲜花 +5 收起 理由
wayne + 5 是前9项

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-8 23:25:15 | 显示全部楼层
63# zgg___
帅呆了!
zgg的代码启发了我,
我看能不能改一下贪心的策略。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-9 09:18:40 | 显示全部楼层
zgg在63楼的和Fans在47楼给的的有点差别。
在n=10时,开始分道扬镳了。
Fans可否给出n=10时,r=51的数据?
zgg能给出r=52的方案:

1.png                                2.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-9 09:29:39 | 显示全部楼层
63# zgg___
太棒了。
Sort[Split[Sort]] 比 Tally 效率高多了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-6-9 10:51:44 | 显示全部楼层
64#wayne
虽然zgg___和KeyTo9_Fans的前9项数据相同,但是按47#KeyTo9_Fans的说明,只有前6项数据是确定无改的,而n>6以后的数据都可能有进一步优化的空间。
我猜想,对于n<=6,KeyTo9_Fans一定是使用了穷举算法,对于n>6,则使用了类似于贪心算法的优化算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-6-9 10:59:34 | 显示全部楼层
使用41#wayne的程序计算了n=9时点(x,y)所关联的正方形数,结果如下图:
9.png
51#所写的公式在奇数的情况下仍然成立,原点仍然在大正方形中心,这时点(x,y)的坐标都是半整数。比如图中标识49的点的坐标为(±1/2,±1/2)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-6-9 17:38:35 | 显示全部楼层

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

评分

参与人数 1威望 +12 金币 +12 鲜花 +12 收起 理由
wayne + 12 + 12 + 12 完全正确!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-7-23 21:09 , Processed in 0.055020 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表