平成２４年９月２日
[流れ星]
第２７９回数学的な応募解答
＜解答募集期間：8月12日～9月2日
［不定方程式の解］
ｘ，ｙ，ｎは０以上の整数とするとき、次の不定方程式・不定不等式の解の個数を求めてください。
（１）不定方程式 ２ｘ＋ｙ＝２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
（２）不定方程式 ２ｘ＋ｙ＝２ｎ＋１の解（ｘ，ｙ）の組の個数をｎで表わせ。
（３）不定不等式 ２ｘ＋ｙ≦２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
（４）100円、50円、10円の硬貨を使って840円をちょうど支払う方法（それぞれの硬貨の枚数）は何通りあるか。ただし、全種類の硬貨を用いなくても良い。
ＮＯ１「uchinyan」 08/12 12時43分受信
「uchinyan」 08/12 14時48分受信
更新9/2
（１）不定方程式 ２ｘ＋ｙ＝２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
x = 0 ～ n に対して y = 2n - 2x と一意に決まるので，n+1 個。
（２）不定方程式 ２ｘ＋ｙ＝２ｎ＋１の解（ｘ，ｙ）の組の個数をｎで表わせ。
x = 0 ～ n に対して y = 2n+1 - 2x と一意に決まるので，n+1 個。
（３）不定不等式 ２ｘ＋ｙ≦２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
2x + y
= m，m = 0, 1, 2, ..., 2n，の解の個数を足し上げればいいので，
m = 2k，k = 0 ～ n と m = 2k+1，k = 0 ～ n-1 に分けて，(1)と(2)の結果を使って，
Σ[k=0,n]{k+1}
+ Σ[k=0,n-1]{k+1}
= 2 *
Σ[k=0,n-1]{k+1} + (n+1)
= 2 *
n(n+1)/2 + (n+1) = n(n+1) + (n+1) = (n+1)^2 個
（４）100円、50円、10円の硬貨を使って840円をちょうど支払う方法
（それぞれの硬貨の枚数）は何通りあるか。ただし、全種類の硬貨を用いなくても良い。
100円，50円，10円の硬貨を，x 枚，y 枚，z 枚，x >= 0，y >= 0，z >= 0，使うとすると，
100x +
50y + 10z = 840，10x + 5y + z = 84，5(2x + y) + z = 84
u = 2x
+ y とおくと，u >= 0，5u + z =
84，z = 84 - 5u
u = 0 ～ 16 に対して z は一意に決まり，2x
+ y <= 16 となるので，
(3)の結果，n = 8，を使って，(8+1)^2 = 9^2 = 81 通り。
(別解1) 検算その１ 図形的に
(1)，(2)，(3)は (x,y)-座標系で考えると，解の (x,y) はいわゆる格子点になります。
(1)の解は，直線 y = - 2x + 2n 上の格子点なので，
(0,2n),
(1,2n-2), (2,2n-4), ..., (n-1,2), (n,0) の n+1 個。
(2)の解は，直線 y = - 2x + 2n+1 上の格子点なので，
(0,2n+1),
(1,2n-1), (2,2n-3), ..., (n-1,3), (n,1) の n+1 個。
(3)の解は，直線 y = - 2x + 2n，x 軸，y 軸，で囲まれた直角三角形の内部及び周上の格子点なので，この直角三角形を二つ用意し斜辺でくっつけて長方形を作って考えると，
求める個数
= ((出来上がる長方形の内部及び周上の格子点の個数) + (斜辺上の格子点の個数))/2
=
((n+1)(2n+1) + (n+1))/2 = (n+1)(2n+2)/2 = (n+1)^2 個。
(4)は，３次元で図形的に考えるのは大変なので，格子点を数えるエッセンスだけを単純に，
100x +
50y + 10z = 840，10x + 5y + z = 84，
5y + z
= 84 - 10x >= 0，0 <= x <= 8，
x = 84
- 10x - 5y >= 0，0 <= y <= 16 - 2x，
求める個数
=
Σ[x=0,8]{Σ[y=0,16-2x]{1}} = Σ[x=0,8]{17 - 2x}
= 17 *
9 - 2 * (8 * 9)/2 = 17 * 9 - 8 * 9 = 9 * 9 = 81 個
(別解2) 検算その２ 場合の数で
(1)は，2x + y = 2n より y は偶数なので，y = 2u とおくと，
x + u =
n，x >= 0，u >= 0
これは，2 種類のボールを重複を許して合計 n 個取ってくる場合の数と同じなので，
2Hn =
(n+1)Cn = n+1 通りで，(x,u) の組，したがって (x,y)
の組としては n+1 個。
(2)は，2x + y = 2n+1 より y は奇数なので，y = 2u+1 とおくと，
x + u =
n，x >= 0，u >= 0
これは，(1)と同じなので，(x,u) の組，したがって (x,y) の組としては n+1 個。
(3)は，2x + y = m，m
= 0, 1, 2, ..., 2n，の解の個数を足し上げればいいので，
m = 2k，k = 0 ～ n と m = 2k+1，k = 0 ～ n-1 に分けて考えて，
x + u =
k，k = 0 ～ n の個数の２倍から x + u = n の個数を引いたもの，です。
前者は v >= 0 として x + u + v = n として考えた場合の (x,u,v) の個数の２倍と同じで，
3Hn * 2
= (n+2)Cn * 2 = (n+2)(n+1)/2 * 2 = (n+2)(n+1) 個，
後者は n+1 個，なので，
求める個数 =
(n+2)(n+1) - (n+1) = (n+1)^2 個。
(4)は，100x + 50y + 10z = 840，10x + 5y + z = 84。
z = 5u
+ 4，u >= 0，とおくと，10x + 5y
+ (5u + 4) = 84，2x + y + u = 16。
ここで，y + u
は偶数になるので，y，u が両方とも偶数か両方とも奇数になります。
y = 2v，u = 2w，v >= 0，w
>= 0，の場合は，2x + 2v + 2w = 16，x
+ v + w = 8。
これは，3 種類のボールを重複を許して合計 8 個取ってくる場合の数と同じなので，
3H8 =
10C8 = (10 * 9)/2 = 45 通りで，(x,v,w) の組，したがって (x,y,z) の組としては 45
個。
y =
2v+1，u = 2w+1，v >= 0，w >= 0，の場合は，2x + (2v+1) + (2w+1) = 16，x + v + w = 7。
これは，3 種類のボールを重複を許して合計 7 個取ってくる場合の数と同じなので，
3H7 =
9C7 = (9 * 8)/2 = 36 通りで，(x,v,w) の組，したがって (x,y,z) の組としては 36
個。
そこで，これらの和になるので，
求める個数 =
45 + 36 = 81 個。
(感想) これは見事な誘導問題になっていますね。どちらかというと基本的な積み重ねで，よい演習問題だと思います。なお。検算も兼ねて，別解を二つほど書いてみました。
ＮＯ２「ｽﾓｰｸﾏﾝ」 08/12 22時14分受信 更新9/2
問題
ｘ，ｙ，ｎは０以上の整数とするとき、次の不定方程式・不定不等式の解の個数を求めてください。
（１） 不定方程式 ２ｘ＋ｙ＝２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
yが0,2,…,2nまでのn+1通り
（２） 不定方程式 ２ｘ＋ｙ＝２ｎ＋１の解（ｘ，ｙ）の組の個数をｎで表わせ。
y-1=z と考えれば…z-1が0,2,…,2nまでのn+1通り
（３） 不定不等式 ２ｘ＋ｙ≦２ｎの解（ｘ，ｙ）の組の個数をｎで表わせ。
2nまでに偶数は0,2,…,2n のn+1通り…(n+1)(n+2)/2
奇数は1,3,…,2n-1 のn通り…(n＋1)n/2
合計＝(n+1)(n+2)/2＋(n＋1)n/2=（n＋１）^2 通り
（４）100円、50円、10円の硬貨を使って840円をちょうど支払う方法（それぞれの硬貨の枚数）は何通りあるか。ただし、全種類の硬貨を用いなくても良い。
10x+5y+z=84
z-4=m とすると…
10x+5y+m=80
m=5k
2x+y+k=16
y+k=2z
y+k は…0,2,…,16 の17通り
2H0+2H2+2H4+2H6+2H8+2H10+2H12+2H14+2H16
=1C0+3C2+5C4+7C6+9C8+11C10+13C12+15C14+17C16
=1+3+5+7+9+11+13+15+17
=18*4+9
=9*9
=81 通り
ＮＯ３「Iga」 08/14 04時27分受信 更新9/2
（１）もとの不定方程式を ｙ＝－２ｘ＋２ｎ と一次関数の形に変形する。
不定方程式の解は、直線ｙ＝－２ｘ＋２ｎ（ｘ≧０、ｙ≧０）上の格子点
で表される。すなわち、（０，2n），（１，2n-2），…，（ｎ，０）で、
その個数は、（ｎ＋１）個となる。
（２）（１）と同様にｙ＝－２ｘ＋２ｎ＋１と変形して考える。
不定方程式の解、すなわち直線上の格子点は（０，2n+1），（１，2n-1），…，（ｎ，１）
なので、その個数は（ｎ＋１）個
（３）同様の変形をすると、ｙ≦－２ｘ＋２ｎ
その解は、ｘ軸、ｙ軸、直線ｙ＝－２ｘ＋２ｎ に囲まれた
直角三角形内（線上を含む）の格子点で表される。
すなわち、ｘ＝０のとき ｙ＝2n,2n-1,2n-2，…，０ の（２ｎ＋１）通り
ｘ＝１のとき、ｙ＝2n-2,2n-3,2n-4,…，０ の（２ｎ－１）通り
ｘ＝２のとき、ｙ＝2n-4,2n-5,2n-6，…，０ の（２ｎ－３）通り
… … …
ｘ＝ｎのとき ｙ＝０ の １ 通り
よって（２ｎ＋１）＋（２ｎ－１）＋（２ｎ－３）＋…＋１＝ｎ^2
解の個数は ｎ＾２個
（４）８４０円のうち、４０円は１０円玉４枚以外の支払い方法はないので、
８００円を３種の硬貨で支払うと考えてもよい。
さらに、１０円玉の枚数は、１００円玉と５０円玉の枚数により一意に決まるので、
除外して考えてよい。
１００円玉ｘ枚、５０円玉ｙ枚で、８００円以下を支払う方法は
不定不等式 １００ｘ＋５０ｙ≦８００ の解で表される。
両辺を５０で割って ２ｘ＋ｙ≦１６
これは（３）でｎ＝８の場合だから、解の個数（支払いの方法）は ６４通り
「Iga」 08/17 00時41分受信 更新9/2
（３）が違ってました。
誤 よって（２ｎ＋１）＋（２ｎ－１）＋（２ｎ－３）＋…＋１＝ｎ^2
正 よって（２ｎ＋１）＋（２ｎ－１）＋（２ｎ－３）＋…＋１＝（ｎ＋１）＾２
解の個数は （ｎ＋１）＾２ 個
なので（４）は
両辺を５０で割って ２ｘ＋ｙ≦１６
これは（３）でｎ＝８の場合だから、解の個数（支払いの方法）は
（８＋１）＾２＝ ８１ 通り
ＮＯ４「にいばりZ12」08/15 03時52分受信
「にいばりZ12」08/18 01時54分受信 更新9/2
（１）
２ｘ＋ｙ＝２ｎを変形すると ｙ＝２（ｎ-ｘ）
ｘ，ｙ，ｎは０以上の整数なので
ｎ≧ｘ、ｎが0を含むのでｘのとり得る値の個数はｎ+1
よって（ｘ，ｙ）の組はｎ+1個・・・答
（２）
２ｘ＋ｙ＝２ｎ+1を変形すると ｙ＝２（ｎ-ｘ）+1
ｘ，ｙ，ｎは０以上の整数なので
ｎ≧ｘ、ｎが0を含むのでｘのとり得る値の個数はｎ+1
（n=0のときx=1とするとy<0となることに注意）
よって（ｘ，ｙ）の組はｎ+1個・・・・（（１）と同じになる）・・・答
（３）
（１）で２ｘ＋ｙ＝２ｎの解（ｘ，ｙ）の組の個数は得ているので ２ｘ＋ｙ＝２ｋとし
ｋ=0,1,2・・・ｎ+1の解の個数の総和をとればよい
（この時、2ｋ＝0,2,4,8・・・2(n-1),2n）
解の個数をS1とすると
S1=1＋2+3+4+・・・ｎ+1＝（ｎ+2）（ｎ+1）/2
（２）の結果から２ｘ＋ｙ≦２ｎ+1の解（ｘ，ｙ）の組の個数も同じ。
しかしながら２ｘ＋ｙ＝２ｎ+1の解は２ｘ＋ｙ≦２ｎを満たさないので
２ｘ＋ｙ＝２ｎ-1（２ｘ＋ｙ＝２ｎはカウント済み）の解の総和を加えると
ｎに関して0と正の整数の条件を満たします。
この解をＳ2とすると
Ｓ2＝1＋2+3+4+・・・ｎ-1＝（ｎ+1）（ｎ）/2
Ｓ=Ｓ1+Ｓ2＝（ｎ+2）（ｎ+1）/2+（ｎ+1）（ｎ）/2
Ｓ=Ｓ1+Ｓ2＝（ｎ+1）＾2・・・・答
（４）
100ｘ＋50ｙ+10ｚ＝840という不定方程式を解く問題になります。
変形して
２ｘ＋ｙ＝（84-Z）/5
右辺分子は5の倍数にならければならないことから
ｚ＝5ｋ-1（17≧ｋ≧1、ｋは整数）
よってｚの取りうる個数は17個
ｚ並べると
4,9,14,19,24・・・・84
右辺を並べると
16,15,14,13,12、・・・0
左辺は（１）（２）と同じ形です
右辺は（１）（２）の合計の形（ただし（2）については2ｎ-1）になっているので
２ｘ＋ｙ≦2ｎ
ｎ＝８を解けばよいことになり（3）と同値の問題になります
よって（３）の結果を利用し
S=（8+1）＾2＝81
となり81通り・・・解答
別解
第２７２回（格子点は何個）の問題と同様に解きます
（１）
２ｘ＋ｙ＝２ｎが格子点と交わる個数（ｘ軸、y軸を含む）なので
（ｘ，ｙ）の組はｎ+1個
（２）
２ｘ＋ｙ＝２ｎ+1が格子点と交わる個数（ｘ軸、y軸を含む）なので
（ｘ，ｙ）の組はｎ+1個
（３）
２ｘ＋ｙ＝２ｎとｘ軸、y軸に囲まれる格子点のうちyが奇数となる点を除いた個数は
1＋2+3+4+・・・ｎ+1＝（ｎ+2）（ｎ+1）/2
一方でyが奇数となる点も２ｘ＋ｙ≦２ｎを満たすので
２ｘ＋ｙ＝２ｎとｘ軸、y軸に囲まれる格子点のうちyが奇数となる個数は
1＋2+3+4+・・・ｎ-1＝（ｎ+1）（ｎ）/2
これらを足し合わせると（ｎ+1）＾2
またｙ＝2ｎとｘ＝ｎおよびｘ軸、y軸に囲まれる格子点をすべて足すと
（ｎ＋１）×（2ｎ+1）
２ｘ＋ｙ＝２ｎとｘ軸、y軸 に囲まれる格子点は上記格子点の1/2に
（ｎ+1）/2を加えた個数になるので
（ｎ＋１）×（2ｎ+1）/2+（ｎ+1）/2＝（ｎ+1）＾2
さらに、格子点長方形を２でわって回答を得るには
ｙ＝2ｎ+1とｘ＝ｎおよびｘ軸、y軸に囲まれる格子点をすべて足して２でわる方法があります
結果は同じですが、
（（ｎ+1）×（2ｎ+2））/2
（4）ではこの方法をとります。
（４）
（3）よりｘ＝ｎとｙ＝2ｎ+1とｘ軸、y軸に囲まれる格子点の1/2の個数となるので
ｎ＝8として
（（ｎ+1）×（2ｎ+2））/2＝（9×9×2）/2＝81
（感想）
いつもながら、（4）を解くために順次（1）、（2）、（3）と誘導させて（4）の解き方に気づかせる出題には感銘を受けます。
いきなり（4）を主題されたらお手上げだったと思います。
今回は、不定方程式の一般的解法（アルゴリズム？）がよくわからなかったのでまったくの我流で解きました。別解は紙に一生懸命線を引いて確かめた結果です。
ＮＯ５「浜田明巳」 08/17 17時10分受信 更新9/2
（１）２ｘ＋ｙ＝２ｎ
ｙ＝２(ｎ－ｘ)≧０から，０≦ｘ≦ｎ
ｘ＝０のとき，ｙ＝２ｎ
ｘ＝１のとき，ｙ＝２(ｎ－１)
ｘ＝２のとき，ｙ＝２(ｎ－２)
・・・
ｘ＝ｎのとき，ｙ＝０
故に(ｘ，ｙ)の個数は，(ｎ＋１)個
（２）２ｘ＋ｙ＝２ｎ＋１
ｙ＝２(ｎ－ｘ)＋１≧０から，０≦ｘ≦ｎ＋１／２ ∴０≦ｘ≦ｎ
ｘ＝０のとき，ｙ＝２ｎ＋１
ｘ＝１のとき，ｙ＝２(ｎ－１)＋１
ｘ＝２のとき，ｙ＝２(ｎ－２)＋１
・・・
ｘ＝ｎのとき，ｙ＝１
故に(ｘ，ｙ)の個数は，(ｎ＋１)個
（３）２ｘ＋ｙ≦２ｎ
２ｘ＋ｙ＝２ｋ（０≦ｋ≦ｎ）のとき，（１）から，
１，２，３，・・・，ｎ＋１
個ずつ．
故に合わせて，
１＋２＋３＋・・・＋(ｎ＋１)＝(ｎ＋１)(ｎ＋２)／２（個）
２ｘ＋ｙ＝２ｋ－１（１≦ｋ≦ｎ）のとき，（２）から，
１，２，３，・・・，ｎ
個ずつ．
故に合わせて，
１＋２＋３＋・・・＋ｎ＝ｎ(ｎ＋１)／２（個）
まとめると，
(ｎ＋１)(ｎ＋２)／２＋ｎ(ｎ＋１)／２＝{(ｎ＋２)＋ｎ}(ｎ＋１)／２＝(ｎ＋１)２（個）
（４）１００円をｘ個，５０円をｙ個，１０円をｚ個（ｘ，ｙ，ｚは０以上の整数）とすると，
１００ｘ＋５０ｙ＋１０ｚ＝８４０
∴１０ｘ＋５ｙ＋ｚ＝５(２ｘ＋ｙ)＋ｚ＝８４
∴２ｘ＋ｙ＝(８４－ｚ)／５
２ｘ＋ｙは０以上の整数であるので，０≦８４－ｚ≦８４，８４－ｚは５の倍数となり，
８４－ｚ＝０，５，１０，・・・，８０
∴ｚ＝８４，７９，７４，・・・，４
このとき，
２ｘ＋ｙ＝０，１，２，・・・，１６
これは，（３）のｎ＝８の場合である．
故に答は，(８＋１)２＝８１（通り）
（別解）１０ｘ＋５ｙ＋ｚ＝８４
５ｙ＋ｚ＝１０(８.４－ｘ)≧０から，０≦ｘ≦８.４ ∴０≦ｘ≦８
ｘ＝０のとき，５ｙ＋ｚ＝８４
∴ｚ＝５(１６.８－ｙ)≧０
∴０≦ｙ≦１６.８ ∴０≦ｙ≦１６
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，１７通り．
ｘ＝１のとき，５ｙ＋ｚ＝７４
∴ｚ＝５(１４.８－ｙ)≧０
∴０≦ｙ≦１４.８ ∴０≦ｙ≦１４
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，１５通り．
ｘ＝２のとき，５ｙ＋ｚ＝６４
∴ｚ＝５(１２.８－ｙ)≧０
∴０≦ｙ≦１２.８ ∴０≦ｙ≦１２
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，１３通り．
ｘ＝３のとき，５ｙ＋ｚ＝５４
∴ｚ＝５(１０.８－ｙ)≧０
∴０≦ｙ≦１０.８ ∴０≦ｙ≦１０
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，１１通り．
ｘ＝４のとき，５ｙ＋ｚ＝４４
∴ｚ＝５(８.８－ｙ)≧０
∴０≦ｙ≦８.８ ∴０≦ｙ≦８
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，９通り．
ｘ＝５のとき，５ｙ＋ｚ＝３４
∴ｚ＝５(６.８－ｙ)≧０
∴０≦ｙ≦６.８ ∴０≦ｙ≦６
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，７通り．
ｘ＝６のとき，５ｙ＋ｚ＝２４
∴ｚ＝５(４.８－ｙ)≧０
∴０≦ｙ≦４.８ ∴０≦ｙ≦４
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，５通り．
ｘ＝７のとき，５ｙ＋ｚ＝１４
∴ｚ＝５(２.８－ｙ)≧０
∴０≦ｙ≦２.８ ∴０≦ｙ≦２
ｙの１つの値に対して，ｚは０以上の整数として一意的に定まる．
故にこのとき，３通り．
ｘ＝８のとき，５ｙ＋ｚ＝４
∴ｚ＝５(０.８－ｙ)≧０
∴０≦ｙ≦０.８
∴ｙ＝０，ｚ＝４
故にこのとき，１通り．
故にまとめると，
１＋３＋５＋・・・＋１７＝９×(１＋１７)／２＝８１（個）
（別解）
いつものようにエクセルのマクロでも解いてみた．上記と同じ答が得られた．
Option Explicit
Const n_max As Integer = 100
Sub Macro12()
Dim n As Integer
Dim x As Integer
Dim y As Integer
Dim j As Integer
For j = 0 To 1
Sheets("Sheet" & Right(Str(j + 1), 1)).Select
Cells(1, 1).Value = "n"
Cells(1, 2).Value = "個数"
For n = 0 To n_max
Cells(n + 2, 1).Value = n
Cells(n + 2, 2).Value = 0
Range("A" & (n + 2)).Select
For x = 0 To n
y = 2 * n - 2 * x + j
Cells(n + 2, 2).Value = Cells(n + 2, 2).Value + 1
Next x
Next n
Range("A1").Select
Next j
End Sub
Sub Macro3()
Dim n As Integer
Dim x As Integer
Dim y As Integer
Dim j As Integer
Sheets("Sheet3").Select
Cells(1, 1).Value = "n"
Cells(1, 2).Value = "個数"
For n = 0 To n_max
Cells(n + 2, 1).Value = n
Cells(n + 2, 2).Value = 0
Range("A" & (n + 2)).Select
For j = 0 To 2 * n
For x = 0 To Int(j / 2)
y = j - 2 * x
Cells(n + 2, 2).Value = Cells(n + 2, 2).Value + 1
Next x
Next j
Range("A1").Select
Next n
End Sub
Sub Macro4()
Dim x As Integer
Dim y As Integer
Dim z As Integer
Sheets("Sheet4").Select
Cells(1, 1).Value = 0
For x = 0 To Int(84 / 10)
For y = 0 To Int((84 - 10 * x) / 5)
z = 84 - 10 * x - 5 * y
Cells(1, 1).Value = Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value, 2).Value = x
Cells(Cells(1, 1).Value, 3).Value = y
Cells(Cells(1, 1).Value, 4).Value = z
Range("B" & Cells(1, 1).Value).Select
Next y
Next x
Range("A1").Select
End Sub
ＮＯ６「kasama」 08/23 16時12分受信
更新9/2
|
不定方程式の代数学的解法はよく見掛けますが、グラフを描いて視覚的にアプローチしてみました。 |
||||||||||||||||||||||||||||||||||||||||
|
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。
