平成１６年５月１６日

[流れ星]

　　　　　第１３７回数学的な応募問題解答

　　　　　　＜解答募集期間：４月２５日〜５月１５日＞
［格子点の数］

　太郎さんは入試問題集をみています。次のような問題を見つけました。

ｘ、ｙ、ｚおよびｎを０または正の整数とする。

問題１：不等式ｘ＋ｙ≦３を満たす組（ｘ、ｙ）の個数を求めよ。

問題２：不等式ｘ＋ｙ≦ｎを満たす組（ｘ、ｙ）の個数を求めよ。

問題３：不等式ｘ＋ｙ＋ｚ≦ｎを満たす組（ｘ、ｙ、ｚ）の個数を求めよ。

問題４：不等式ｘ/３＋ｙ≦ｎを満たす組（ｘ、ｙ）の個数を求めよ

＜出典：京都産業大学1996年＞

ＮＯ１「toru」　　 4/27: 11時29分受信 更新5/16更新
問題１　(x,y)=(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(3,0)の10個
問題２　x+y+ω=n を満たす(x,y,ω) (x,y,ω=0,1,2,------,n)と同じことで、これは３個からn個を選ぶ重複組み合わせで、
3Ｈn=3+n-1Ｃn=(n+1) (n+2) /2
問題３　x+y+z+ω=nを満たす(x,y,z,ω) (x,y,z,ω=0,1,2,-----,n)と同じことで、
これは4個からn個を選ぶ重複組み合わせで、4Ｈn=4+n-1Ｃn=(n+1) (n+2)(n+3) /6
問題４　問題２でx=0のものはy=0,1,----,nのn+1個、他はn(n+1)/2個 
問題２のx=k(k=1,2,----n) に対してx=3k-2,3k-1,3kを対応させれば、求める個数はn+1+3n(n+1)/2=(n+1)(3n+2)/2

問題１３７の解答を送ります。y=k の時x=0,----の何個あるのこれをΣでk=0〜nまでたし合わせてというのが普通でしょうが、
ちょっと変えてみましたがどんなもんでしょうか？　

ＮＯ２「kasama」１回目 4/27: 13時17分受信 更新5/16更新
今回は格子点の数に関する入試問題ですね。最近、受験数学とほとんど縁がないので、どのような解法が一般的なのかはよくわかりません。効率良く得点できる方法が好まれるのでしょうね。

いろんなアプローチがあるかと思いますが、直感的にわかり易いので、幾何学的な解釈で格子点の数を求めることが多いのではないでしょうか。私も試験でこのような問題に出会ったら、たぶんそのようなやり方をするでしょう。でも、試験と違って時間的な余裕がありますから、いろんなやり方があった方が面白いので、漸化式で考えてみました。
「kasama」２回目 4/30: 12時58分受信
「kasama」３回目 5/11: 15時15分受信 更新5/16更新（一緒にして）
問題１
組(x,y)を単純に洗い出すと、以下の10個です。
　(0,0),(0,1),(0,2),(0,3),
　(1,0),(1,1),(1,2),
　(2,0),(2,1),
　(3,0)

問題２
漸化式で考えます。x+y≦nを満たす組(x,y)の個数をS_n(x, y)と表します。
すると、S_n(x,y)は S_n-1(x, y)にx+y=nを満たす組(x,y)の個数を加算したものと考えられます。そして、x+y=nを満たす組(x,y)の組は、以下のn+1個です。
　(0,n),(1,n-1),･･･,(n,0)
したがって、
　S_n(x,y) = S_n-1(x,y) + n + 1　⇒　S_n(x,y) - S_n-1(x,y) = n + 1
となり、この差分方程式の一般解を求めればよいわけです。やり方はいろいろあると思いますが、例えば、
　S_n(x,y) - S_n-1(x,y) = n + 1
　S_n-1(x,y) - S_n-2(x,y) = n
　S_n-2(x,y) - S_n-3(x,y) = n - 1
　･･･
　S₁(x,y)   - S₀(x,y) = 2
とやって、すべてを加えると、
　S_n(x,y) = S₀(x,y) + 2 + ･･･ + n - 1 + n + n + 1
ここで、S₀(x,y)=1 なので、
　S_n(x,y) = 1 + 2 + ･･･ + n - 1 + n + n + 1 = (n+1)(n+2)/2
となりますから、求める個数は(n+1)(n+2)/2個です。

問題３
前問と同様に考えて、x+y+z=nを満たす組(x,y,z)の組は、以下の(n+1)(n+2)/2個です。
　(0,n,0),(1,n-1,0),･･･,(n,0,0)
　(0,n-1,1),(1,n-2,1),･･･,(n-1,0,1)
　･･･
　(0,0,n)
したがって、
　S_n(x,y,z) = S_n-1(x,y,z) + (n+1)(n+2)/2　⇒　S_n(x,y) - S_n-1(x,y) = (n+1)(n+2)/2
ですから、
　S_n(x,y,z) - S_n-1(x,y,z) = (n+1)(n+2)/2
　S_n-1(x,y,z) - S_n-2(x,y,z) = n(n+1)/2
　･･･
　S₁(x,y,z)   - S₀(x,y,z) = 3
すべてを加えると、S₀(x, y,z)=1なので、
　S_n(x,y,z) = S₀(x,y,z) + 3 + ･･･ + n(n+1)/2 + (n+1)(n+2)/2
　= 1 + n(n² + 6n + 11)/6 = (n+1)(n+2)(n+3)/6
よって、求める個数は(n+1)(n+2)(n+3)/6個です。

問題４
同様にして、n-1<x/3+y≦nを満たす組 (x,y)の組は3n+1個なので、
　S_n(x/3,y) = S_n-1(x/3,y) + 3n + 1　⇒　S_n(x/3,y) - S_n-1(x/3,y) = 3n + 1
とやって、
　S_n(x/3,y) - S_n-1(x/3,y) = 3n + 1
　S_n-1(x/3,y) - S_n-2(x/3,y) = 3n - 2
　･･･
　S₁(x/3,y)   - S₀(x/3,y) = 4
すべてを加えると、S₀(x/3, y)=1なので、
　S_n(x/3,y) = S₀(x/3,y) + 4 + ･･･ + 3n - 2 + 3n + 1
　= (n+1)(3n+2)/2
よって、求める個数は(n+1)(3n+2)/2個です。


【一般化（その１） 2004.4.30追記】
関係式をa₁+a₂+･･･ +a_k≦n と一般化します。よく考えてみると、a₁+a₂+･･･ +a_k=iの組(a₁,a₂,･･･, a_k)は重複組合せですね。例えば、i個のみかんをk人に配る場合数_kH_i(=_k+i-1C_i) と同じですね。
なので、a₁+a₂+･･･ +a_k≦nの場合数は、_kH_iの総和となり、
　 _{n                n                    n}
　Σ_kH_i = Σ_k+i-1C_i = Σ_{(k-1) + iCi} = _k+nC_n = _k+nC_k
　^{i=0              i=0                  i=0}
です（補足参照）。よって、
　a₁+a₂+･･･ +a_k≦nの場合数は_k+nC_nまたは_k+nC_k個
です。

ちなみに、問題１、２、３について個数を計算してみると、
　問題１･･･₃₊₂C₂ = 10
　問題２･･･_n+2C₂ = (n+2)(n+1)/2
　問題３･･･_n+3C₃ = (n+3)(n+2)(n+1)/6
となります。

【一般化（その２）2004.4.30追記】
関係式をa₁/m₁+a₂/m₂+･･･ +a_k/m_k≦n （ただし、m_i(i=1,2,･･･,k)は自然数）と一般化します。この先はできていません。すみません。もう少しお時間を下さい。⇒私の力では、一般化はできませんでした（2004.5.11追記）。


【補足】
_n+1C_r = _nC_r + _n-1C_r-1 + _n-2C_r-2 + ･･･ + _n-rC₀　 (r≦n)

［証明]
漸化式_nC_r = _n-1C_r + _n-1C_r-1を以下のように繰り返し適用することによって、上式を導くことができます。
_n+1C_r = _nC_r + _nC_r-1
       = _nC_r + (_n-1C_r-1 + _n-1C_r-2)
       = _nC_r + _n-1C_r-1 + (_n-2C_r-2 + _n-2C_r-3)
       ･･･
       = _nC_r + _n-1C_r-1 + ･･･ + _n-r+1C₁ + _n-r+1C₀
       = _nC_r + _n-1C_r-1 + ･･･ + _n-r+1C₁ + 1
       = _nC_r + _n-1C_r-1 + ･･･ + _n-r+1C₁ + _n-rC₀

ＮＯ３「BossF」　　4/29: 03時12分受信 更新5/16更新
問題１

与式 ⇔ x≦3-y だから、ある y に対し 3-y+1=4-y 個づつ x はきまる

よって、0≦y≦3に注意すれば 1+2+3+4=10個…答

問題2

問題1と同様にして 1+2+…+(n+1)=(n+1)(n+2)/2個…答

問題3

与式 ⇔ x+y≦n-z で、問題2より ある z に対して(n-z+1)(n-z+2)/2 個づつ( x,y) はきまる

0≦ｚ≦nだから　��(z=0to n)[(n-z+1)(n-z+2)/2]

                       =(n+1)^2・(n+2)/2-(2n+3)n(n+1)/4+n(n+1)(2n+1)/12

                       =1/12・(n+1){6(n+1)(n+2)-3n(2n+3)+n(2n+1)}

                       =1/12・(n+1)(2n^2+10n+12)

                       =(n+1)(n+2)(n+3)/6 …答

問題4

与式 ⇔ x≦3(n-y) だから、ある y に対し 3(n-y)+1 個づつ x はきまる

0≦y≦nだから　��(y=0to n)[3(n-y)+1]=(n+1)(3n+1)-3n(n+1)/2

                                                   =(n+1)(3n+2)/2…答

ＮＯ４「kashiwagi」4/29: 08時04分受信 更新5/16更新
137回解答

まず、一般式　　を考える。これは　　と同値である。

後半の式はｘ、ｙ　各々の軸とｎで交わる勾配が−１のグラフである。図を描くのが面倒なので申し訳ございませんが理論的な説明のみでお許し下さい。

　即ち、４点（0,0 ）（0,n ）（n,0 ）（n,n ）で囲まれた正方形の内部及び線上の格子点数の半分が求めるものである。

　上記式上の格子点＋（正方形上ないし内部の格子点−上記式上の格子点）/２＝

　（ｎ＋１）＋〔（ｎ＋１）^２−（ｎ＋１）〕/２＝（ｎ＋１）（ｎ＋２）/２

以上が一般式の場合である。

問１．

ｎに３を代入して、求めるものは10となる。

問２．

上記で議論したものであるから、（ｎ＋１）（ｎ＋２）/２が求めるもの。

問３．

　　図形的にはｘ、ｙ及びｚ　各々の軸とｎで交わる三角錐の平面上と内部の格子点が求めるものである。ｚ＝０、１、・・・・ｎで三角錐を切断した平面上の格子点を総計したものであるから、問２の結果を利用し、

　＝（ｎ＋１）（ｎ^２＋５ｎ＋６）/６

問４．

　　　は問２のｘ　切片を３ｎ　に置き換えたものであるから、問２と全く同様にして、（ｎ＋１）（３ｎ＋２）/２　を得る。

ＮＯ５「たけクジラ」4/30: 2時03分受信 更新5/16更新
こんにちわ、お久しぶりです。たけくじらです。今回はいろいろなやり方で解いてみました。
これからも受験勉強の一環として気の向いた問題は解いていきたいです。
ｘ、ｙ、ｚおよびｎを０または正の整数とする。
問題１：不等式ｘ＋ｙ≦３を満たす組（ｘ、ｙ）の個数を求めよ。

(0,0)(0,1)(1,0)(0,2)(1,1)(2,0)(0,3)(1,2)(2,1)(3,0)
より、1+2+3+4=10
10個
問題２：不等式ｘ＋ｙ≦ｎを満たす組（ｘ、ｙ）の個数を求めよ。

xy平面の第一象限において、この不等式を満たす格子点はx+y=k(0<=k<=n)
の整数解。また、これはkが増えるごとにひとつずつ増えていくので
（なぜならば、x+y=mのとき、解は(m,0)(m-1,1)(m-2,2)
…(1,m-1)(0,m)よって、m+1個。同じようにx+y=m+1のとき、解はm+2個。）
よって解の個数は(n+1)(n+2)/2

問題３：不等式ｘ＋ｙ＋ｚ≦ｎを満たす組（ｘ、ｙ、ｚ）の個数を求めよ。

ここで、xにkを入れたときを考えると、y+z<=n-kでなければならない。よって、(y,z)の個数は(n-k+1)(n-k+2)/2
このkが[0,n]を動くため
n
Σ(n-k+1)(n-k+2)/2=(n+1)(n^2+5n+6)/6
0

問題４：不等式ｘ/３＋ｙ≦ｎを満たす組（ｘ、ｙ）の個数を求めよ

与式⇔x+3y<=3n
ここでyにkをいれたとする。すると、x<=3n-3k　よって
n
Σ(3n-3k)=3n(n+1)/2
0

ＮＯ６「浜田明巳」 5/01: 11時21分受信 更新5/16更新

ここをクリック下さい。「報告」です。（一考察です）

ＮＯ７「三角定規」 5/04: 11時07分受信 更新5/16更新

いつも，考えて面白い問題の提供，有難うございます。

お送りするレポートには，「すべて知っていますよ」を装い，考察のエッセンス部分しか書いていません。しかしながら内実は，((3)などは）素朴な数え上げから始まり，頭の錆を音を立てて落としながら，「あ，階差数列になっているんだ！」などど感激しながら解いております。

ＮＯ８「中川幸一」 5/15: 5時03分受信 更新5/16更新

　　　　＜自宅＞　　mizuryu@aqua.ocn.ne.jp