OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

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

  • 困ってます
  • 質問No.106921
  • 閲覧数1749
  • ありがとう数4
  • 気になる数0
  • 回答数5
  • コメント数0

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

 。 。 。 。 。
 。 。 。 。 。
 。 。 。 。 。
 。 。 。 。 。
 。 。 。 。 。
 
正直言えば、プレゼントクイズなのですが…(^^;
教えてください。答えと解法
通報する
  • 回答数5
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.5
レベル14

ベストアンサー率 57% (1014/1775)

正直で、よろしいっ!

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

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

●最初の辺は出発点と、もう一つの点を繋ぐ。このもう一つの点が出発点に対して、下に幾つ、右に幾つずれているか、を考えます。下へのずれを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進んで、2つ目の辺は右にS進む。残りの2つの辺は左へ進むだけなので、考えなくて良い。だから、「幅」は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=1のとき C(1,0)+C(1,1)+...................+C(1,N-2)
S=2のとき 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の2乗の意味です。)
ここで
(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

●計算間違いはしょっちゅうやりますんで、チェック宜しく。
お礼コメント
noname#5824

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

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

ありがとうございました。
投稿日時 - 2001-07-20 14:26:26
-PR-
-PR-

その他の回答 (全4件)

  • 回答No.1
レベル11

ベストアンサー率 33% (131/392)

格子点の記号を下のようにします。 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を左上に格子点を持つ正方形は4個です。 B1を左上に格子点を持つ正方形は3個です。 C1を左上に格子点を持つ正方形は2個です。 D1を左上に格子点を持つ正方形は1個です。 A2を左上に格子点を ...続きを読む
格子点の記号を下のようにします。

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を左上に格子点を持つ正方形は4個です。
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

です。


  • 回答No.2
レベル13

ベストアンサー率 31% (302/946)

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、 ...続きを読む
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個
お礼コメント
noname#5824

早速の回答ありがとうございます…
ですが、お二人とも「斜めの正方形」が抜けてません?
実は、それがやっかいなので悩んでいるのですが…
投稿日時 - 2001-07-20 11:50:47
  • 回答No.3
レベル10

ベストアンサー率 9% (16/172)

そこまで分かっているなら、後は数えるだけかと思いますが。
そこまで分かっているなら、後は数えるだけかと思いますが。
  • 回答No.4
レベル10

ベストアンサー率 33% (34/103)

2つの整数の組(i, j) (1≦i≦n, 0≦j≦n, i+j≦n)に対し、1つの正方形の角度と大きさが重複なく決まります。 つまり、点O(0, 0)、点A(i, j)、点B(i-j, i+j)、点C(-j, i)として正方形OABCと角度・大きさが同じ正方形です。 重複なくと言うのはある(i, j)に対する正方形と、(i, j)とは異なる整数の組(i', j')に対する正方 ...続きを読む
2つの整数の組(i, j) (1≦i≦n, 0≦j≦n, i+j≦n)に対し、1つの正方形の角度と大きさが重複なく決まります。
つまり、点O(0, 0)、点A(i, j)、点B(i-j, i+j)、点C(-j, i)として正方形OABCと角度・大きさが同じ正方形です。

重複なくと言うのはある(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
と言うわけで50個入ります。
お礼コメント
noname#5824

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

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

とても役に立ちました。ありがとうございました。
投稿日時 - 2001-07-20 14:22:29
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ