免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 正方形个数

本帖最后由 hejoseph 于 2017-1-18 19:58 编辑

这是一个旧问题了:方格本中以相邻的 $m$ 行和相邻的 $n$ 列的平行线交点为顶点的正方形有多少个?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

假定最小的格子边长为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].)
1.先来算正方形的边平行于m行n列的个数(比如x=0或y=0).
  边长为1的有mn个,边长为2的有(m-1)(n-1)个,.....,边长为m-1的有2(n-m+2),边长为m的有n-m+1个.
2.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)个;.....
.....这样下去,没得到简单点的表达式.

TOP

不妨不设是线,就设是格,设就是$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}$个。最后的用了软件算不知道前面的对不对。

TOP

回复 3# abababa

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

TOP

回复 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$是偶数)

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

TOP

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

TOP

$m=2$,$n=2$时有多少个?

TOP

回复 7# xugaosong

6个

TOP

本帖最后由 hejoseph 于 2017-1-21 09:43 编辑

1.png
2017-1-21 09:00

当 $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$ 就是结果。

TOP

返回列表 回复 发帖