平成２５年７月７日

[流れ星]

　　　　　第２９３回数学的な応募解答

　　　　　　＜解答募集期間：６月16日〜７月７日＞

［三角錐内の格子点］

座標がすべて整数である点を格子点という。次の領域内にある格子点の個数をＳ_ｎ　を求めよ。

問題１：　ｙ≧０、ｚ≦≧０、３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳ_ｎ　を求めよ。

問題２　ｘ≧０、　ｙ≧０、ｚ≧０、６ｘ＋３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳ_ｎ　を求めよ。

ただし、ｎは自然数とする。

＜水の流れ：。お詫び問題１を　ｙ≧０、ｚ≧０、３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳ_ｎ　を求めよ。赤のように修正します。６月１６日午後１５時訂正＞

NO1「uchinyan」 06/16 12時57分受信 更新7/7

問題１：ｙ≧０、ｚ≦≧０、３ｙ＋２ｚ≦６ｎ のとき、格子点の個数をＳｎを求めよ。

上記は「2013年6月16日12:40」の時点での問題文ですが，

この z に関する式は明らかにおかしいです。

また，題意がよく分からないのですが，問題１：は問題２：への誘導と思われ，

Sn が有限の値で意味をもつように， (y,z) は２次元平面における格子点で，

y >= 0，z >= 0，3y + 2z <= 6n のとき，格子点の個数 Sn を求めよ。だと思って解きます。

(解法1)　(y,z) は，0 <= y <= 2n，0 <= z <= [3n - 3y/2]，の整数，なので，

Sn = Σ[y=0,2n]{Σ[z=0,[3n-3y/2]]{1}}

= Σ[k=0,n]{Σ[z=0,3n-3k]]{1}} + Σ[k=1,n]{Σ[z=0,3n-3k+1]]{1}}

= Σ[k=0,n]{3n - 3k + 1} + Σ[k=1,n]{3n - 3k + 2}

= {3n * 1 - 3 * 0 + 1 * 1} + 2 * Σ[k=1,n]{3n - 3k + 1} + {1 * n}

= (4n + 1) + 2 * (3n * n - 3 * n(n+1)/2 + 1 * n)

= 3n^2 + 3n + 1 個

(解法2)　　対象となっている領域は，(y,z)-２次元座標平面上で，

(0,0)，(2n,0)，(0,3n) を頂点とする三角形の内部又は(頂点を含む)辺

です。そこで，三角形の内部の格子点の個数を I，辺上の格子点の個数を B とすると，

ピックの定理より，　三角形の面積 = I + B/2 – 1　ここで，

三角形の面積 = 2n * 3n * 1/2 = 3n^2

B = 3n + 2n + n = 6n

なので，

3n^2 = I + 6n/2 - 1，I = 3n^2 - 3n + 1

これより，

Sn = I + B = (3n^2 - 3n + 1) + 6n = 3n^2 + 3n + 1 個　になります。

問題２：ｘ≧０、ｙ≧０、ｚ≧０、６ｘ＋３ｙ＋２ｚ≦６ｎ のとき、格子点の個数をＳｎを求めよ。

(解法1)

(x,y,z) は，0 <= x <= n，0 <= y <= 2n - 2x，0 <= z <= [3n - 3x - 3y/2]，の整数，なので，

Sn = Σ[x=0,n]{Σ[y=0,2n-2x]{Σ[z=0,[3n-3x-3y/2]]{1}}}

= Σ[x=0,n]{Σ[k=0,n-x]{Σ[z=0,3n-3x-3k]]{1}} + Σ[k=1,n-x]{Σ[z=0,3n-3x-3k+1]]{1}}}

= Σ[x=0,n]{Σ[k=0,n-x]{3n - 3x - 3k + 1} + Σ[k=1,n-x]{3n - 3x - 3k + 2}}

= Σ[x=0,n]{{3n * 1 - 3x * 1 - 3 * 0 + 1 * 1} + 2 * Σ[k=1,n-x]{3n - 3x - 3k + 1} + {1 * (n-x)}}

= Σ[x=0,n]{(4n - 4x + 1) + 2 * (3n * (n-x) - 3x * (n-x) - 3 * (n-x)(n-x+1)/2 + 1 * (n-x))}

= Σ[x=0,n]{(3n^2 + 3n + 1) - (6n+3)x + 3x^2}

= (3n^2 + 3n + 1) * (n+1) - (6n+3) * n(n+1)/2 + 3 * n(n+1)(2n+1)/6

= (n+1)(2n^2 + 4n + 2)/2

= (n+1)^3 個

(解法2)

6x + 3y + 2z <= 6n，3y + 2z <= 6(n-x)

と書けるので，0 <= x <= n より，

0 <= x <= n-1 のとき，(y,z) の個数 = 問題１：の S(n-x)

x = n のとき，(y,z) = (0,0)，(y,z) の個数 = 1

そこで，

Sn = Σ[x=0,n-1]{問題１：の S(n-x)} + 1

= Σ[k=1,n]{問題１：の S(k)} + 1

= Σ[k=1,n]{3k^2 + 3k + 1} + 1

= Σ[k=1,n]{(k+1)^3 - k^3} + 1

= (n+1)^3 個

(感想)

問題１：の問題文が少しおかしかったので，適当に解釈して解きました。これでよかったでしょうか。ある意味オールマイティな解法を(解法1)に，この問題の意図と思われる解法を(解法2)にしました。

問題２：の結果は美しいですね。

この結果からすると，今は思い付いていませんが，他の面白い解法があるのかも知れませんね

＜水の流れ：実は、別解として、３次元の格子点でピックの公式を使って 解けないかとは思っていまして、＞

＜uchinyanからのコメント＞06/1７ １０時５３分受信

実は同じことを思って少し考えてみたのですがうまくいかず，
Webで調べてみたところ，少なくとも一般の場合は望み薄のようです。
http://www.geocities.jp/ikuro_kotaro/koramu/531_p1.htm
http://www.geocities.jp/ikuro_kotaro/koramu/1520_dv2.htm
http://okwave.jp/qa/q3186023.html
http://mathworld.wolfram.com/EhrhartPolynomial.html
など。

もっとも，今回の問題の三角すいはかなり単純なので何かあるかも，
と思うのですが，どのみち，面上の格子点を数える必要はありそうで，
となると，今回の誘導に従った(解法2)辺りが一番簡単なのかな，
という気もしています。

NO2「ｽﾓｰｸﾏﾝ」　　06/18 00時08分受信

「ｽﾓｰｸﾏﾝ」　　06/21 16時40分受信 更新7/7

問題１：　ｙ≧０、ｚ≧０、３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳｎ　を求めよ。
0<=y<=2n, 0<=z<=3n
y<=2n-2z/3
グラフで…この直線上の格子点の数を求めると…
z が3の倍数のときだけ直線上に乗っているので…
n+1個
けっきょく…
{(2n+1)(3n+1)-(n+1)}/2+(n+1)=(6n^2+6n+2)/2=3n^2+3n+1 個

問題２　ｘ≧０、　ｙ≧０、ｚ≧０、６ｘ＋３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳｎ　を求めよ。
ただし、ｎは自然数とする。

0<=6x<=6n-3y-2z
6x+3y+2z=6n の平面上に乗っている格子点の数を求める…
問題1の結果を使うと…
3y=6n-2z 上には、n+1個の格子点があった…
つまり…

6n=3y+2z
6x=6n-3y-2z において、x=0 のときのもの…
x=1 なら…
6(n-1)=3y+2z
0<=x<=n なので…
次々、スライスした場合をカウントした和を求めればいいはず...で...

Σ[0<=k<=n] (3k^2+3k+1)
=(n+1)n(2n+1)/2+3n(n+1)/2+n+1
=n^3+3n^2+3n+1

ってことになるのかな ^^…

NO3「浜田明巳」　06/18 12時46分受信

「浜田明巳」　06/18 16時17分受信 更新7/7

エクセルのマクロで前記の結果を検証してみた．
　１≦ｎ≦１０００の範囲のみであるが，確かに問題１では，Ｓ_ｎ＝３ｎ^２＋３ｎ＋１，問題２では，Ｓ_ｎ＝(ｎ＋１)^３となった．

Option Explicit
Sub Macro1()
     Dim y As Long
     Dim n As Long
     Dim Sn As Long
     For n = 1 To 1000
         Sn = 0
         For y = 0 To Int(6 * n / 3)
             Sn = Sn + Int((6 * n - 3 * y) / 2) + 1
         Next y
         If Sn = S(n) Then
             Cells(n + 1, 1).Value = n
             Cells(n + 1, 2).Value = Sn
         Else
             Cells(n + 1, 1).Value = ""
             Cells(n + 1, 2).Value = ""
         End If
     Next n
End Sub
Private Function S(ByVal n As Long) As Long
     S = 3 * n * n + 3 * n + 1
End Function

Option Explicit
Sub Macro2()
     Dim x As Long
     Dim y As Long
     Dim n As Long
     Dim Sn As Long
     For n = 1 To 1000
         Sn = 0
         For x = 0 To Int(6 * n / 6)
             For y = 0 To Int((6 * n - 6 * x) / 3)
                 Sn = Sn + Int((6 * n - 6 * x - 3 * y) / 2) + 1
             Next y
         Next x
         If Sn = S(n) Then
             Cells(n + 1, 1).Value = n
             Cells(n + 1, 2).Value = Sn
         Else
             Cells(n + 1, 1).Value = ""
             Cells(n + 1, 2).Value = ""
         End If
     Next n
End Sub
Private Function S(ByVal n As Long) As Long
     S = (n + 1) * (n + 1) * (n + 1)
End Function

「浜田明巳」　06/19 17時52分受信 更新7/7

問題１：ｙ≧０，ｚ≧０，３ｙ＋２ｚ≦６ｎ
　ｋを整数とする．
　０≦ｚ≦３ｎ−３／２・ｙであるから，
i).ｙ＝２ｋのとき，０≦ｚ≦３ｎ−３ｋ
　故にｚは(３ｎ−３ｋ＋１)＝{３ｎ−３・(ｙ／２)＋１}個ある．
ii). ｙ＝２ｋ−１のとき，０≦ｚ≦３ｎ−３ｋ＋１.５
　故にｚは(３ｎ−３ｋ＋２)＝{３ｎ−３・(ｙ＋１)／２＋２}個ある．

　次に３ｙ＋２ｚ≦６ｎから，０≦ｙ≦２ｎ
　　∴Ｓ_ｎ＝Σ_{ｙ＝０，２，４，………，２ｎ}{３ｎ−３・(ｙ／２)＋１}
　　　　　　＋Σ_{ｙ＝１，３，５，………，２ｎ−１}{３ｎ−３・(ｙ＋１)／２＋２}
　　　　　＝Σ_{ｋ＝０，１，２，………，ｎ}(３ｎ−３ｋ＋１)
　　　　　　＋Σ_{ｋ＝１，２，３，………，ｎ}(３ｎ−３ｋ＋２)
　　　　　＝(３ｎ＋１)＋Σ_{ｋ＝１，２，３，………，ｎ}(３ｎ−３ｋ＋１)
　　　　　　＋Σ_{ｋ＝１，２，３，………，ｎ}(３ｎ−３ｋ＋２)
　　　　　＝３ｎ＋１＋Σ_{ｋ＝１，２，３，………，ｎ}{(３ｎ−３ｋ＋１)＋(３ｎ−３ｋ＋２)}
　　　　　＝３ｎ＋１＋Σ_{ｋ＝１，２，３，………，ｎ}(６ｎ−６ｋ＋３)
　　　　　＝３ｎ＋１＋３Σ_{ｋ＝１，２，３，………，ｎ}{(２ｎ＋１)−２ｋ}
　　　　　＝３ｎ＋１＋３{(２ｎ＋１)ｎ−２・１／２・ｎ(ｎ＋１)}
　　　　　＝３ｎ＋１＋３{ｎ(２ｎ＋１)−ｎ(ｎ＋１)}
　　　　　＝３ｎ^２＋３ｎ＋１

問題２：ｘ≧０，ｙ≧０，ｚ≧０，６ｘ＋３ｙ＋２ｚ≦６ｎ
　３ｙ＋２ｚ≦６(ｎ−ｘ)（ｎ−ｘ＝０，１，２，………，ｎ）
であるから，求める個数は，問題１のＳ_ｎを使って表すと，
　　Ｓ_０＋Ｓ_１＋Ｓ_２＋………＋Ｓ_ｎ
となる．
　３ｙ＋２ｚ≦６・０のとき，(ｙ，ｚ)＝(０，０)となり，Ｓ_０＝１
　故に非負整数ｎにおいて，Ｓ_ｎ＝３ｎ^２＋３ｎ＋１
　　∴Ｓ_０＋Ｓ_１＋Ｓ_２＋………＋Ｓ_ｎ
　＝Σ_{０≦ｋ≦ｎ}Ｓ_ｋ
　＝Σ_{０≦ｋ≦ｎ}(３ｋ^２＋３ｋ＋１)
　＝１＋Σ_{１≦ｋ≦ｎ}(３ｋ^２＋３ｋ＋１)
　＝１＋３・１／６・ｎ(ｎ＋１)(２ｎ＋１)＋３・１／２・ｎ(ｎ＋１)＋ｎ
　＝１／２・ｎ(ｎ＋１){(２ｎ＋１)＋３}＋(ｎ＋１)
　＝ｎ(ｎ＋１)(ｎ＋２)＋(ｎ＋１)
　＝(ｎ＋１){ｎ(ｎ＋２)＋１}
　＝(ｎ＋１)^３
　これが問題２で求めるＳ_ｎとなる．

ＮＯ４「二度漬け白菜」7/4 12時54分受信 更新7/7

問題２：

S_n=(n+1)^3 . (答え)

一般に、x≧0, y≧0, z≧0, 6x＋3y+2z≦N (Nは任意の自然数)
を満たすような整数の組(x,y,z)の個数をA(N)として考えてみます。
A(N)は 6x＋3y+2z+w=N, x≧0, y≧0, z≧0, w≧0
を満たすような整数の組(x,y,z,w)の個数に等しいです。
このことから数列{A(N)}の母関数 Σ[k=0〜∞]A(k)*x^k が
 1/((1-x)*(1-x^2)*(1-x^3)*(1-x^6))　---(☆)
であることがわかります。
(☆)を部分分数分解すればA(N)を求めることができます。

A(N)=floor(1/18*(-3*floor((N+2)/3)+3*floor(N/3)+2)*(floor(N/3)+1)+1/432*(N+6)*(2*N^2+24*N+47+9*(-1)^N)+7/36)
となります。
https://oeis.org/A029000

これを使って S_n を計算すると、　
S_n=A(6*n)
=floor(1/18*(-3*2*n+3*2*n+2)*(2*n+1)+1/432*(6*n+6)*(2*(6*n)^2+24*6*n+47+9)+7/36)
=floor(n^3+3*n^2+3*n+13/12)
=n^3+3*n^2+3*n+1
=(n+1)^3.

Ｎｏ５「にいばりZ12」 7/5 23時46分受信 更新7/17

問題１：　ｙ≧０、ｚ≧０、３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳ_ｎ　を求めよ。ただし、ｎは自然数とする。

ｙ＝2ｎ

ｚ＝3ｎ

ｙ軸、z軸に囲まれる格子点の和は

(2n+1)×（3ｎ+1）＝６ｎ＾2+5ｎ+1

求める格子点はのこの約半分になります。

3ｙ+2ｚ＝6ｎ（ｙ≧０、ｚ≧０）上の格子点は求める領域に入るので

この線分上の格子点の1/2を（6ｎ＾2+5ｎ+1）/2に加えると回答となります。

3ｙ+2ｚ＝6ｎを変形整理しｙ＝2ｋ、ｚ＝3（ｎ-ｋ）とおくとｎ≧ｋ≧０の範囲で恒等式となり

3ｙ+2ｚ＝6ｎ上の0を含む格子点の数はｎ+1となります。

よって求める格子点は（6ｎ＾2+5ｎ+1）/2+（ｎ+1）/2

Ｓ_ｎ＝3ｎ＾2+3ｎ+1・・・・・回答（自然数ｎに0を含む場合）

Ｓ_ｎ＝3ｎ＾2+3ｎ＝3n(ｎ+1)・・・・・回答（自然数ｎに0（ｙ＝ｚ＝0）を含まない場合）

因みに約半分と言うのは

limｎ→∞（3ｎ＾2+3ｎ+1）/（6ｎ＾2+5ｎ+1）

=limｎ→∞（3+3/ｎ+1／ｎ＾2）/（6 +5/ｎ+1/ｎ＾2）＝1/2

問題２　ｘ≧０、　ｙ≧０、ｚ≧０、６ｘ＋３ｙ＋２ｚ≦６ｎ　のとき、格子点の個数をＳ_ｎ　を求めよ。

式を変形すると

3ｙ+2ｚ≦6（ｎ-ｘ）

となります。

ここで

ｎ<ｘ　とすると

ｙorｚ<0となるので

0≦ｘ≦ｎ

問題1から、ｘ=0の場合Ｓ_ｎ’＝3ｎ＾2+3ｎ+1

格子点は0≦ｘ≦ｎの範囲で求めればよいので

Σ〈i=0→ｎ〉（3ｉ＾2+3ｉ+1）＝ｎ（ｎ+1）（2ｎ+1）/2　+　３ｎ(ｎ＋１）/2　+　ｎ+1

Ｓ_ｎ＝（ｎ+1）＾3・・・・・回答（自然数ｎに0を含む場合）

Ｓ_ｎ＝（ｎ+1）^3-1＝n(ｎ＾2+3ｎ+3)・・・・・回答（自然数ｎに0（ｘ＝ｙ＝ｚ＝0）を含まない場合）

＜水の流れ：ｎが自然数ですから、０以外でも（ｘ＝ｙ＝ｚ＝0）を数えても差し支えないです＞

＜にいばりZ12からのコメント：7/７ ０時２１分受信 更新7/17

ところで、時々悩むと言うか迷うのですが、自然数の考え方です。

いつも忘れるのでウィキで確認すると、数論の場合0を含まない、集合論の場合含む流儀が採られているとあります。

自然数の成り立ちや語感からは０を含まないと言うのが妥当な気もします。

問題１では、含まないほうが回答として綺麗ですが、問題２は含むほうが簡潔です。

そのようなわけで両方併記させて頂いたわけですが、グラフ化すると確かに原点が欠けているのは如何にも不自然です。

学校では今どちらを採用しているのかわかりませんが、数学界で統一見解を出してほしいものです。（子供たちも迷うのではないでしょうか？特に数学好きな子供なら）

「浜田明巳」　07/09 09時19分受信 更新7/10

自然数の定義であるが，数学の授業では，正の整数としている．そう扱って間違いはない．授業や入試でも，すべてそうなっている．ただ，学問の分野によっては，そう扱ってない場合もあると聞く．実際，私が高校でＢＡＳＩＣを習ったころ（何十年か前である）の，情報の先生（その頃は情報と呼んではおらず，単に数学の先生だった）は，自然数を０以上の整数として，プログラムを説明していた．混乱を招くようであれば，自然数を使わず，正の整数としたらよいであろう．数列の漸化式の問題では，自然数ではなく，ｎ＝１，２，３，・・・としている．不正確な表現ではあるが，実質的に間違いはない．

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。