$ $
(1) 주어진 격자에서 찾을 수 있는 $1 \times 1$ 크기의 정사각형의 수는 모두 $mn$개이다. 또한 이 격자에서 찾을 수 있는 $2 \times 2$ 크기의 정사각형의 수는 모두 $(m-1)(n-1)$개이다. 일반적으로 $1 \leq k \leq m$에 대하여 $k \times k$ 크기의 정사각형의 수는
\[ (m-k+1)(n-k+1) \]
이 됨을 쉽게 확인할 수 있다. 따라서 이 격자에서 찾을 수 있는 모든 정사각형의 개수는
\[ \sum_{k=1}^{m} (m-k+1)(n-k+1) \]
을 계산하면 얻을 수 있다. 이제 계산을 간단히 하기 위하여 $j = m-k+1$의 치환을 이용하면
\[ \begin{aligned} \sum_{k=1}^{m} (m-k+1)(n-k+1) &= \sum_{j=1}^{m} j(j-m+n) \\ &= \sum_{j=1}^{m} j^2 - (m+n)j \\ &= \frac{m(m+1)(2m+1)}{6} - \frac{m(m+1)(m+n)}{2} \\ &= \frac{m(m+1)(3n-m+1)}{6} \end{aligned} \]
를 얻는다..
(2) 주어진 격자 위의 직사각형은 대각선 상에 위치한 두 점으로부터 완전히 결정되기 때문에, 주어진 격자에서 직사각형을 하나 찾는 것은 같은 행이나 같은 열에 위치하지 않는 서로 다른 두 점을 찾는 것과 같다. 이 때, 위의 조건을 만족하는 두 점의 택하는 경우의 수는 $m \times n$ 격자 위에서 임의로 한 점을 택하고, 그 점이 위치한 행과 열을 제외한 $(m-1) \times (n-1)$ 격자 위에서 나머지 한점을 찾는 경우의 수와 같다. 따라서 이 경우의 수는
\[ (m+1)(n+1) \times mn \]
으로 주어진다. 하지만 하나의 직사각형 $ABCD$에 대하여 이 직사각형의 대각선상에 위치한 두 점은 $\{(A,\,C),\, (C,\,A),\, (B,\,D),\, (D,\,B)\}$로 총 네번 반복되어 세어지므로,
\[ \frac{mn(m+1)(n+1)}{4} \]
가 원하는 답임을 알 수 있다..