论坛 › 难题征解 › 格点正方形，可否发现一个新数列？

wayne 发表于 2012-5-29 14:15:14

9# hujunhua
额，老大竟然先得到答案
:L

hujunhua 发表于 2012-5-29 22:04:30

不能说得到答案了，这才刚开头呢，真正要解决的是第2问。

简单交代一下是怎么得到8#公式的。

为了“认识”一个斜置正方形ABCD，我们考虑刚好可套住它的水平正方形，称为ABCD的house.
将具有相同大小的house的所有格点正方形归于一个类Class(m), m就是house的边长。
wayne 在4#隐含指出，边长为m的house共有(n-m+1)^2个, 而一个house包含Class(m)的m个成员。
所以Class(m)共有m(n-m+1)^2个成员.
将上述式子从m=1~n累加，即得到8#的公式。

wayne 发表于 2012-5-30 11:48:11

12# hujunhua
:b:

==========
第二问，我可以给一个下限值。
对于n*n，即每边有n+1个点的情况。

四个顶点均在最外围的边上的正方形有n个。所以外围的四个边至少要抹掉 n 个点。
同理，里边的就是n-2个，。。。。
于是总共至少要抹掉n+ (n-2) +....= floor((n+1)^2/4) 个点
即

n=2, 至少是大于2
n=3, 至少是大于4
n=4, 至少是大于6

wayne 发表于 2012-5-30 11:51:48

好像挺弱的

wayne 发表于 2012-5-30 14:01:12

n=2 时，至少要抹掉3个点，总共有32种图案。
n=3 时，至少要抹掉6个点，总共有232种图案。

KeyTo9_Fans 发表于 2012-5-30 15:27:29

$n=0$：$0$
$n=1$：$1$
$n=2$：$3$
$n=3$：$6$
$n=4$：$10$
$n=5$：$15$

猜想：挖掉的点数至少为$(n(n+1))/2$。

#####

挖掉的点数是$A000217(n)$。

留下的点数是$A000217(n+1)$。

#####

恭喜你：

http://oeis.org/A000217

里面没有记载，你可以把这个问题写上去了。

wayne 发表于 2012-5-30 16:13:47

对于n*n，即每边有n+1个点的情况。
不妨建立坐标，设左下角为(0,0)点，往左是横轴正向，向上是纵轴正向。
根据对称性，我们不妨 先确定必须抹掉原点(0,0)。

四个顶点均在 曲线 xy(x-m)(y-m) =0 上的正方形我们看做为一类，称为Class m，
总共有m个，所以至少要抹掉 m 个点。这m个点安排在 曲线 (x-m)(y-m) =0 上。

于是 对 m从1到n求和。 即是 n(n+1)/2

hujunhua 发表于 2012-5-30 16:14:08

竟然是三角数啊，那还写个啥劲！

wayne 发表于 2012-5-30 16:25:38

18# hujunhua
给三角数增加新的内涵，新的诠释呀！

KeyTo9_Fans 发表于 2012-5-30 16:36:11

可以写的，在$A000217$的 COMMENTS 上写：

$a(n)=$maximum number ofpoints in an $n\times n$ grid that do not contain a square with all corners on them.

$a(n)=$minimum number of points needed to remove from the $(n+1)\times (n+1)$ grid, such that there is no square with all corners on them.

查看完整版本: 格点正方形，可否发现一个新数列？