正方形个数

hejoseph

这是一个旧问题了：方格本中以相邻的 $m$ 行和相邻的 $n$ 列的平行线交点为顶点的正方形有多少个？

realnumber

假定最小的格子边长为1，建立坐标系，使得这些点的坐标为(0,0),(m,0),(0,n),(m,n)四点围成的矩形内（包括边）的整点，不妨设$m\le n$，
　　　四点(i,j),(i+x,j+y),(i+x+y,j+y-x),(i+y,j-x)可以围成正方形（横坐标范围[0,m],纵坐标范围[0,n]．）
１．先来算正方形的边平行于m行n列的个数（比如x=0或y=0）．
  边长为1的有mn个，边长为2的有(m-1)(n-1)个，.....，边长为m-1的有2(n-m+2)，边长为m的有n-m+1个．
２．x=1,y=1,有(n-1)(m-1)个；x=1,y=2，有(n-2)(m-2)个；x=1,y=3,有(n-3)(m-3)个;.......;x=1，y=m-2,有(n-m+1)个.
      x=2,y=1,有(n-2)(m-2)个；.....
.....这样下去，没得到简单点的表达式．

abababa

不妨不设是线，就设是格，设就是$m \times n$格的，$m<n$，这时最大的正方形就是$m \times m$的，$m$方向上只有$1$个，$n$方向上有$n-m+1$个。
第二大的是$(m-1) \times (m-1)$的，$m$方向有$2$个，$n$方向有$n-m+2$个。
总共就是$\sum_{i=1}^{m}i(n-m+i)=\frac{m(m+1)(3n+1-m)}{6}$个。最后的用了软件算不知道前面的对不对。

abababa

回复 3# abababa

哦，还有那种斜着的，这就不容易算了。

abababa

回复 4# abababa
对角线与方格线重合时：
下设$x \times x$表示的是对角线与方格线重合的正方形，且对角线长是$x$。当$m$是奇数时，最大的是$m \times m$的正方形，$m$方向有$2$个，$n$方向有$n-m$个，若$m$是偶数则$m$方向有$1$个，$n$方向有$n-m$个。最小的是$2 \times 2$的。

总共是$\sum_{i=0}^{m-3}(i+2)(n-m+i)=\frac{(m-2)(3mn+3n-m^2-8m-3)}{6}$（$m$是奇数），或$\sum_{i=0}^{m-2}(i+1)(n-m+i)=\frac{m(m-1)(3n-m-4)}{6}$（$m$是偶数）

还有对角线与方格线不平行的情况，暂时还没想明白。

hejoseph

我得到的结果是：当 $m\leqslant n$ 时个数是
\[
\frac{m(m+1)(m+2)(2n-m+1)}{12}
\]

xugaosong

$m=2$，$n=2$时有多少个？

色k

回复 7# xugaosong

6个

hejoseph

当 $m\leqslant n$ 时，首先考察顶点在边长为 $k$（$k$ 是正数）的正方形边上的那些正方形（含边的端点），这样的正方形中可构造出 $k$ 个不同的正方形，上图为边长为 3 的正方形单元内构造出的正方形；而题目中的格点含有 $(m-k+1)(n-k+1)$ 个边长为 $k$ 的正方形单元，所以正方形个数为
\begin{align*}
\sum_{k=1}^m (m-k+1)(n-k+1)k&=\sum_{k=1}^m(k(k-1)(k-2)-(m+n-1)k(k-1)+mnk)\\
&=\frac{(m+1)m(m-1)(m-2)}4-(m+n-1)\cdot\frac{(m+1)m(m-1)}3+mn\cdot\frac{(m+1)m}2\\
&=\frac{m(m+1)(m+2)(2n-m+1)}{12}
\end{align*}

当 $m\geqslant n$ 时上面最后的式子交换下 $m$、$n$ 就是结果。