格子点と正方形の枚数の関係

格子点が並んでいる様子を考えます．
例として４×６のものを考えると

・　・　・　・　・　・
・　・　・　・　・　・
・　・　・　・　・　・
・　・　・　・　・　・

この様になります．
この時，格子点４つを結んで作ることができる正方形の枚数は
3×5+2×4+1×3＝26個と求めることが出来ます．

これを証明によって一般化すると，縦にm・横にn（ただしm<n）の格子点がある時，
格子点４つを結んで作ることができる正方形の枚数は
（m-1）(n-1)+(m-2)(n-2)+・・・+(m-m+1)(n-m+1)枚になることが解ります．

更に，点と辺の長さの関係に注目すると
（m+n-1）×0+（m+n-3）×1+（m+n-5）×2+・・・（m+n+1-2n）×mでも求めることができます，証明は省略します．
（上の例ですと9×0+7×1+5×2+3×3=26）


他の求め方はありますでしょうか？
もしくは，一般化によって何か別の定理が出るといったことはありますでしょうか・・・．

No.1 回答者： ji---san 回答日時： 2008/08/08 15:44

お、なかなか賢いですね。

じゃあ私は

(m-1)(m-2)(6n-4m+3)/6 + (m-1)

です。シグマを計算しただけですが、最も計算コスト(掛け算の回数)が少ない、はず

別の定理はどういうのをさしてらっしゃるのかわかりませんが。。。

この回答への補足

確かにΣ計算でまとめることは可能ですね．

例えば4つの格子点を結ぶ結び方を×に変えても同様の手順で×の個数を求めることが出来ますよね．
そのような一般化や拡張によって，何か他の性質が出てこないかな，と思っているのですが・・・．

補足日時：2008/08/08 22:49