第13回　 問題　（12月5日〜2月4日）

応募問題

0<=x<=1000　0<=y<=√x　を満たす整数の組(x,y)は何通りありますか

解答
二乗して　y^2<=ｘ　　31＾2=961　32^2=1024から　Y=0,1,2,3．．31

(ｘ、y)の全てのペア　1001×32=32032から条件を満たさない(X,Y)を除くと考える
Y=0のとき　0個
y=1 のとき　1<=x　から　x=0　１個
y=2 のとき　4<=x　から　x=0,1,2,3　4個
Y=3のとき　9<=X　から　x=0,1,2,3,4,5,6,7,8　9個
...
Y=31の時　31^2<=xから　x=0,1,2,3　...　31^2-1　　31^2個
よって
32032-Σ(k=1から31まで）k^2=32032-31×32×63/6=21616個
　　　

解答２
(0,0)、(N^2,0)、(N^2,N)　（0,N）で囲まれる長方形の中の条件を満たす点の数をA(N)とすると
A(N)とA(N-1)の差は((N-1)^2+1、0)、(N^2,0)　((N-1)^2+1、N-1)、(N^2,N-1)で囲まれる長方形の周および内部の点の
数になるので　N(N^2-(n-1)^2)となる。　このことから

1+2*(4-1)+3*(3**2-2**2)+.....+31*(31**2-30**2)+32*(1000-960)
=sigma(k=1 to 31) k*(k**2-(k-1)**2)+1280
=sigma(k=1 to 31) (2*k**2-k)+1280

sigma(k=1 to n) (2*k**2-k)=1/6*n*(n+1)*(4n-1)
で、n=31とおき、

sigma(k=1 to 31) (2*k**2-k)＝1/6*31*32*123＝20336で
合計＝21616