格子点が作る正方形の総数

方針

解答

⓪ 発想 — どう考え始めるか。 軸に平行な正方形は簡単だが、傾いた正方形は向きも大きさもばらばらで、直接数えると収拾がつかない。

そこで、どの傾いた正方形にも「外接する軸平行の正方形」がただ1つあることに注目する(4頂点のそれぞれを通る水平線・垂直線で囲めばよい)。逆に、1辺 $s$ の軸平行正方形の中には、下辺の分点の取り方1つにつき、傾いた内接正方形が1個できる。

この1対1対応で、「枠ごとに数える」方針に切り替える。

① 軸に平行な正方形。 1辺 $s$($s=1,2,3,4$)のものは、左下の頂点の置き方から $(5-s{)}^2$ 個:

$$4^2+3^2+2^2+1^2=16+9+4+1=30\text{個}$$

② 傾いた正方形。 1辺 $s$ の軸平行正方形を外接枠とする傾いた正方形は、下辺の分点を左から $a$($a=1,\dots ,s-1$)の位置に取るごとに1個(4頂点は各辺を $a:s-a$ に分ける点)。つまり枠1つにつき $s-1$ 個。

③ 合計する。 枠のサイズごとに

$$\sum _{s=1}^4(5-s{)}^2(s-1)=16\cdot 0+9\cdot 1+4\cdot 2+1\cdot 3=20\text{個}$$

よって総数は

$$30+20=50\text{個}$$

まとめ: ばらばらに見えるものは「必ず付いてくる枠」で分類する。外接正方形という枠を経由すると、傾いた正方形が(枠の位置)×(分点の位置)という2つの自由度に分解されて、漏れも重複もなく数えられる。

発展 — 一歩先へ。 ①と②は ${\sum }_{s=1}^4(5-s{)}^2\cdot s$ と1本にまとまる(枠1つにつき、まっすぐ1個+傾き $s-1$ 個で計 $s$ 個)。$n\times n$ の格子でも同じ式 $\sum s(n+1-s{)}^2$ が通用する。$n$ が大きくなるほど、傾いた正方形の割合が増えていくのも、この式から読める。

別解

辺ベクトルでパラメータ化する(得意な人向け)。 正方形を「1辺のベクトル」で名付けると、まっすぐも傾きも1つの式で数えられる。

正方形の1辺を、右上向きのベクトル $(p,q)$($p\ge 1,q\ge 0$)で表す。$q=0$ なら軸平行、$q\ge 1$ なら傾いた正方形だ。この正方形がちょうど収まる外接枠は1辺 $s=p+q$ の軸平行正方形で、枠の置き方は $(5-s{)}^2$ 通り。

よって総数は

$$\sum _{\begin{array}{c}p\ge 1,q\ge 0\\ p+q\le 4\end{array}}(5-p-q{)}^2=\sum _{s=1}^{4}s(5-s{)}^2=1\cdot 16+2\cdot 9+3\cdot 4+4\cdot 1=50$$

($p+q=s$ となる $(p,q)$ がちょうど $s$ 組あることを使った。)

「図形を、それを生成するベクトルで数える」と、場合分け(まっすぐ/傾き)が消えて1本の和になる。分類を減らす方向のパラメータ選びは、数え上げの設計の要だ。