格子点上に出来る正方形の数

下のように縦５横５計２５個の点が格子状に等間隔に
並んでいる時に、４つの点を頂点とする正方形は、
いくつ出来るのか、という問題。

　。　。　。　。　。
　。　。　。　。　。
　。　。　。　。　。
　。　。　。　。　。
　。　。　。　。　。
　
正直言えば、プレゼントクイズなのですが…(^^；
教えてください。答えと解法

No.5 ベストアンサー 回答者： stomachman 回答日時： 2001/07/20 14:16

正直で、よろしいっ！

格子点がN行N列並んでいる場合についてやってみましょう。

●ある頂点から出発して、反時計回りに正方形を描くことにします。そうすると、最初の辺を決めてしまえば正方形が決まりますね。
最初の辺は必ず下もしくは右下の方に進むことに決めましょう。どんな正方形でも、反時計回りに描いたとき４つの辺のうち丁度一つがこの条件を満たします。だから、最初の辺の選び方を尽くせば、全部の正方形が数えられます。

●最初の辺は出発点と、もう一つの点を繋ぐ。このもう一つの点が出発点に対して、下に幾つ、右に幾つずれているか、を考えます。下へのずれをS、右へのずれをMと書きましょう。このような正方形を(S,M)と表します。すると、Sは1,2,3,4,....,N-1のどれか、Mは0,1,2,3,4,....,N-1のどれかです。

●正方形が格子点N×Nから飛び出してしまってはいけませんので、出発点として選べる点と選べない点があることがお分かりでしょう。SとMを決めると、どの点が出発点として選べるかが決まります。そのような点が何個あるかを数えれば、正方形(S,M)の個数が分かります。これをC(S,M)と書くことにします。

●では、出発点として選べる点の数C(S,M)を計算する方法を考えます。
このためには、まず正方形の「幅と高さ」を計算します。「幅」というのは、その正方形が格子点を何列必要とするか。「高さ」とは格子点を何行必要とするか。もちろん「幅」＝「高さ」です。そこで、正方形の「幅と高さ」をW(S,M)と書くことにします。「幅」を考えると、最初の辺が右にM進んで、２つ目の辺は右にS進む。残りの２つの辺は左へ進むだけなので、考えなくて良い。だから、「幅」はM+S。
W(S,M) = M+S
です。
ということは、N列並んでいる格子点のうち、N-W(S,M)列だけから出発点が選べる。またN行並んでいる格子点のうち、N-W(S,M)行だけから出発点が選べる。したがって、
C(S,M) = (N-W(S,M))×(N-W(S,M)) .... N＞W(S,M)のとき
C(S,M) = 0 .... N≦W(S,M)のとき
です。

●正方形が幾つあるか。
C(S,M)＞0の項だけ書くと、
S=１のとき　C(1,0)+C(1,1)+...................+C(1,N-2)
S=２のとき　C(2,0)+C(2,1)+.......+C(2,N-3)
:
S=N-1のときC(N-1,0)
と、これだけあります。Nが5ぐらいだったら、各項を計算していけば出来ますね。

●でも最後まで追いかけてみましょうか。
正方形の数Tは
T=Σ{S=1～N-1} Σ{M=0～N-S-1}[ (N-M-S)^2 ]
（「Σ{i=m～n}[F(n)] 」は F(m)+F(m+1)+.....+F(n)の意味。「x^2」はxの２乗の意味です。）
ここで
(N-M-S)^2 = (N-S)^2 - 2(N-S)M + M^2
従って
T=Σ{S=1～N-1} Σ{M=0～N-S-1}[(N-S)^2 - 2(N-S)M + M^2]
=Σ{S=1～N-1} [Σ{M=0～N-S-1}[(N-S)^2] - Σ{M=0～N-S-1}[2(N-S)M] + Σ{M=0～N-S-1}[M^2]]
=Σ{S=1～N-1} [(N-S)(N-S)^2 - 2(N-S)Σ{M=0～N-S-1}[M] + Σ{M=0～N-S-1}[M^2]]
これに
Σ{M=0～N-S-1}[M] = (N-S-1)(N-S)/2
Σ{M=0～N-S-1}[M^2]= (N-S-1)(N-S)(2(N-S)-1)/6
を代入すると、
T=Σ{S=1～N-1} [(N-S)^3 - (N-S-1)(N-S)^2 + (N-S-1)(N-S)(2(N-S)-1)/6]
ここで、[]内は
(2(N^2)+3N+1)N/6-(1/3)(S^3)+((2*N+1)/2)(S^2)-((6(N^2)+6N+1)/6)S
ですから、
T=(N-1)(2(N^2)+3N+1)N/6
-(1/3)Σ{S=1～N-1}[S^3]
+((2N+1)/2)Σ{S=1～N-1}[S^2]
-((6(N^2)+6N+1)/6)Σ{S=1～N-1}[S]
です。
Σ{S=1～N-1}[S]= N(N-1)/2
Σ{S=1～N-1}[S^2] = (N-1)N(2N-1)/6
Σ{S=1～N-1}[S^3] = ((N-1)N/2)^2
を代入すると、
T=(N-1)(2(N^2)+3N+1)N/6
-(1/3)((N-1)N/2)^2
+(2N+1)(N-1)N(2N-1)/12
-(6(N^2)+6N+1)N(N-1)/12
整理しますと、
T= (N^2-1)(N^2)/12

●計算間違いはしょっちゅうやりますんで、チェック宜しく。

この回答へのお礼

丁寧な回答ありがとうございました。
最初の説明がとてもわかりやすかったので、
その後の式を自分で導くことも出来ました。

人に説明するって難しいですね～（＾＾；
「計算間違い」の件、下の方と回答が同じになるので、
合っていると思います。
一応、チェックはしてみますが…

ありがとうございました。

お礼日時：2001/07/20 14:26

No.4 回答者： taropoo 回答日時： 2001/07/20 14:14

２つの整数の組(i, j) (1≦i≦n, 0≦j≦n, i+j≦n)に対し、１つの正方形の角度と大きさが重複なく決まります。

つまり、点Ｏ(0, 0)、点Ａ(i, j)、点Ｂ(i-j, i+j)、点Ｃ(-j, i)として正方形ＯＡＢＣと角度・大きさが同じ正方形です。

重複なくと言うのはある(i, j)に対する正方形と、(i, j)とは異なる整数の組(i', j')に対する正方形の角度と大きさが同じにはならないと言う意味です。
これは
1≦i≦n, 0≦j≦n
とした事により保証されます。

この角度・大きさの正方形がn*nの格子点上にn(i,j)個入るとすると
n(i, j) = {n - (i + j)}^2
よって、n*nの格子点に含まれる正方形の総数は
Σ{j=0~n-1}Σ{i=1~n-j} n(i, j)
= Σ{j=0~n-1}Σ{i=1~n-j} {n - (i + j)}^2
= Σ{j=0~n-1}Σ{i=1~n-j} i^2
一般解は深追いすると大変な事になるのでこの辺で止めておいて問題のn=5の場合の答えを出しましょう。
Σ{j=0~n-1}Σ{i=1~n-j} i^2
= Σ{j=0~4}Σ{i=1~5-j} i^2
= Σ{i=1~1} i^2 + Σ{i=1~2} i^2 + Σ{i=1~3} i^2 + Σ{i=1~4} i^2
= 1 + (1 + 4) + (1 + 4 + 9) + (1 + 4 + 9 + 16)
= 50
と言うわけで５０個入ります。

この回答へのお礼

こういう回答を待っていました。(;。;)
確かに「数える」っていうのも手だと思うんですけど、
曲がりなりにも数学屋なので…
(なら、自分でやれ、っていうのも聞こえそう…（＾＾；)

何を今さら、と思われると思うんですが、
一般解で考えればよかったんですね。
まず条件式を整えるあたりから勉強しなおします。

とても役に立ちました。ありがとうございました。

お礼日時：2001/07/20 14:22

No.3 回答者： nanashisan 回答日時： 2001/07/20 13:40

そこまで分かっているなら、後は数えるだけかと思いますが。

No.2 回答者： zawayoshi 回答日時： 2001/07/20 10:59

brogieさんのをちょっと拝借

＞格子点の記号を下のようにします。
＞A1,B1,C1,D1,E1
＞A2,B2,C2,D2,E2
＞A3,B3,C3,D3,E3
＞A4,B4,C4,D4,E4
＞A5,B5,C5,D5,E5

辺が1の正方形⇒4×4＝16個
(左上の点がA1～4、B1～4、C1～4、D1～4)
辺が2の正方形⇒3×3＝9個
(左上の点がA1～3、B1～3、C1～3)
辺が3の正方形⇒2×2＝4個
(左上の点がA1～2、B1～2)
辺が4の正方形⇒1×1＝1個
(左上の点がA1のみ)

で、合計30個

この回答へのお礼

早速の回答ありがとうございます…
ですが、お二人とも「斜めの正方形」が抜けてません？
実は、それがやっかいなので悩んでいるのですが…

お礼日時：2001/07/20 11:50

No.1 回答者： brogie 回答日時： 2001/07/20 10:53

格子点の記号を下のようにします。

A1,B1,C1,D1,E1
A2,B2,C2,D2,E2
A3,B3,C3,D3,E3
A4,B4,C4,D4,E4
A5,B5,C5,D5,E5

A1を左上に格子点を持つ正方形は４個です。
B1を左上に格子点を持つ正方形は3個です。
C1を左上に格子点を持つ正方形は2個です。
D1を左上に格子点を持つ正方形は1個です。
A2を左上に格子点を持つ正方形は3個です。
B2を左上に格子点を持つ正方形は3個です。
C2を左上に格子点を持つ正方形は2個です。
D2を左上に格子点を持つ正方形は1個です。
A3を左上に格子点を持つ正方形は2個です。
B3を左上に格子点を持つ正方形は2個です。
C3を左上に格子点を持つ正方形は2個です。
D3を左上に格子点を持つ正方形は1個です。
A4を左上に格子点を持つ正方形は1個です。
B4を左上に格子点を持つ正方形は1個です。
C4を左上に格子点を持つ正方形は1個です。
D4を左上に格子点を持つ正方形は1個です。

4+3+2+1+
3+3+2+1+
2+2+2+1+
1+1+1+1
=30

です。