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

wayne

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

hujunhua

不能说得到答案了，这才刚开头呢，真正要解决的是第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

12# hujunhua ========== 第二问，我可以给一个下限值。 对于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

好像挺弱的

wayne

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

KeyTo9_Fans

$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

对于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

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

wayne

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

KeyTo9_Fans

可以写的，在$A000217$的 COMMENTS 上写： $a(n)=$maximum number of points 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.