第22回　 問題　（10月6日〜11月4日）　

　解答　1791
1/6x+1/10z≦5-y　となりますから　5-y=kとします。
1/6x+1/10z≦k　を満たす(x,z)の個数を数えます。
　

上の図の三角形OABの周および内部にある格子点（座標がともに整数である点）の個数を
調べることにいまうう。。
長方形OABCの周および内部には　(6k+1)(10k+1)個あります。
線分AC上には　(0,10k)　(3,10k-5)　(6,10k-10)　...(6k、0)の2k+1個あります。
これは　z=-5/3x+10kですから傾きを考えるとすぐでます。
三角形OACと三角形ABCは対称ですから
三角形OABの周および内部にある格子点の数は　{(6k+1)(10k+1)+(2k+1)}/2=30k^2+9k+1

実際はk=0,1,2,3,4,5ですから
シグマを使って　30×5×6×11/6+9×5×6/2+5+1=1791としてもよいし
1+40+139+298+517+796=1796となります。

２で割って個数を出すところが　アイデアでしょう(^_^)/そのために問題を作りました。


別解
格子点の個数は
ピックの定理というのがあります。
格子点を結んで得られる多角形(必ずしも凸とは限らない)の面積を S とし
多角形の内部にある格子点の個数を a多角形の辺上にある格子点の個数を b とするとき
S = a + b/2 -1 となります。
これを逆用すると
a+b=S+b/2+1=1/2×6k×10k+(2k+1+6k+10k-1)/2+1=30k^2+9k+1というように出すこともできます。